蓝桥杯 9241.飞机降落

这道题本来作者以为是可以用一些小技巧进行暴力解法的，但是后来试了一下，不能过去全部数据。

下面是对半个的题解：

#include<iostream>
#include<stdio.h>
#include<cstring>
#include<cstdlib>
#include<cmath> 
#include<vector>
#include<algorithm>
#include<stack>
#include<queue>
#include<sstream>
#include<map>
#include<limits.h>
#include<set>
#define MAX 105
#define _for(i,a,b) for(int i=a;i<(b);i++)
#define ALL(x) x.begin(),x.end()
using namespace std;
typedef long long LL;
int n, m, counts=0;
LL A, B;
int res = 0;
struct fly {int times;int pan_xuan;int down;
};
fly a[MAX];
bool cmp(fly a, fly b) {return a.times + a.pan_xuan <= b.times + b.pan_xuan;
}
int main() {ios::sync_with_stdio(false);cin.tie(NULL); cout.tie(NULL);cin >> n;int i = 0;while (n--){i = 0;cin >> m;while (m--) {int t, d, l;cin >> t >> d >> l;a[i].times = t;a[i].pan_xuan = d;a[i].down = l;i++;}sort(a, a + i, cmp);int flag = 1;int sum = 0;_for(j, 0, i) {if (j == 0)sum += a[j].times + a[j].down;else {if (sum <= a[j].times + a[j].pan_xuan) {sum += a[j].down;}else{flag = 0;break;}}}if (flag)cout << "YES" << endl;elsecout << "NO" << endl;}return 0;
}

作者这里犯了一个错误：每一个飞机都有可能是第一个降落的飞机，作者一开始认为是时刻上谁最早谁就先降落，结果并不是那个样子。后面的大体思路其实是正确的。

那么后来就与大佬们讨论一下，发现这个题也是一道DFS的暴力题。

OK，废话不多说，那就开始;

注意这里作者认为，方便的话可以定义结构体进行题解。如果我们开3个数组处理起来会很麻烦。

1.我们看到，有飞机到达的时刻，和盘旋的时间，也就是可以等待的时间，最后就是降落的时间。我们可以得出来什么结论呢？刚开始，我们就可以知道飞机的最早降落时间和最晚降落时间（最早降落时间就是它到达飞机场的时刻，最晚降落时间就是到达时刻加上盘旋的时间），只要飞机在这个时间段之内就可以降落，也就是说，如果第i架飞机想要降落，首先需要知道前面得i-1架飞机降落后总共用到的时间。如果说是在这个时间范围里，那么这个飞机就可以降落；否则不行。

2.我们开始考虑。因为每一架飞机都有可能是第一架飞机的降落，所以这就涉及到一个排序问题了。也就是说，我们可以把这个问题转化为排序型递归的题目。那么，就需要有一个状态函数来判断是否选过这个飞机。OK，那么我们套上模板。终止条件就是当我们遍历到最后一架飞机的时候就可以说是YES了。

有人问，不对呀，不应该是大于飞机的架数才可以吗？假设我们需要降落三架飞机，如果前两架都已经降落了，我们还需要再判断第三架吗？因为第三架都已经是最后一架飞机了，所以我们直接就可以认为这种可能性是可以的。

3.不要忘记，我们只是对于一个飞机深度搜索，我们需要从每一个飞机为起点这样才能覆盖到所有可能性。

注意：在dfs函数中，将要进行递归的时候我用了一个if else语句。这里为什么这样判断呢？你想一下，如果说我们前几架飞机的降落时间还没有下一架飞机的开始时刻多，那么也就是说，我们需要等到下架飞机最早下降的时刻才能进行降落；如果说在下一架飞机的那个允许时间范围内，我们就可以直接接着刚刚已经用过的时间加上下架飞机的降落时间了。

上代码：

#include<iostream>
#include<stdio.h>
#include<cstring>
#include<cstdlib>
#include<cmath> 
#include<vector>
#include<algorithm>
#include<stack>
#include<queue>
#include<sstream>
#include<map>
#include<limits.h>
#include<set>
#define MAX 15
#define _for(i,a,b) for(int i=a;i<(b);i++)
#define ALL(x) x.begin(),x.end()
using namespace std;
typedef long long LL;
int n, m, counts=0;
LL A, B;
int res = 0;
int st[MAX];
bool flag = false;
struct fly {int times;int pan_xuan;int down;
};
fly a[MAX];
void dfs(int nums, int times) {if (nums == m) {flag = true;return;}for (int i = 1; i <= m; i++) {if (!st[i] && times > a[i].times + a[i].pan_xuan)return;if (!st[i] && times <= a[i].times + a[i].pan_xuan) {st[i] = 1;if (a[i].times > times)dfs(nums + 1, a[i].times + a[i].down);elsedfs(nums + 1, times + a[i].down);st[i] = 0;}}
}
int main() {ios::sync_with_stdio(false);cin.tie(NULL); cout.tie(NULL);cin >> n;while (n--) {cin >> m;flag = false;_for(i, 1, m + 1) {cin >> a[i].times >> a[i].pan_xuan >> a[i].down;}_for(j, 1, m + 1) {st[j] = 1;dfs(1, a[j].times + a[j].down);st[j] = 0;}if (flag)cout << "YES" << endl;elsecout << "NO" << endl;}return 0;
}