思路:根据数据范围N<=10猜测用DFS+剪枝,因为菜狗不会状压dp。根据题目,一般这种飞机的题都会用到贪心的思想。思想是每架飞机都要卡极限最早降落时间,从而保证后面的飞机能够有充足时间降落。
代码参考博客@MQy大佬有详细解答
#include <bits/stdc++.h>
using namespace std;
const int N = 10;
int n;
struct Plane {
int t, d, l;
}p[N];
bool vis[N];
bool dfs(int pos, int last){
if(pos == n) return true;
for(int i = 0; i < n; ++i){
int t = p[i].t, d = p[i].d, l = p[i].l;
if(!vis[i] && t + d >= last){
vis[i] = true;
if(dfs(pos + 1, max(last, t) + l)) return true;
vis[i] = false;
}
}
return false;
}
int main(void){
int T;
cin >> T;
while(T--){
scanf("%d", &n);
for(int i = 0; i < n; ++i){
int t, d, l;
scanf("%d%d%d", &t, &d, &l);
p[i] = {t, d, l};
}
memset(vis, 0, sizeof vis);
if(dfs(0,0)) puts("YES");
else puts("NO");
}
return 0;
}