1688成品网站源码下载/搜索引擎付费推广

我们最多有十架飞机，可以选择dfs暴力搜索，枚举每种情况

那么，我们降落的时候怎么确定新的起点也就是newend呢？

如果飞机飞到机场的时刻是大于原来的end的，我们就让ti+li作为newend

否则，我们就让end作为newend

也就是

这种情况就没法降落

这种情况就是从end直接开始降落

这种情况就是从ti开始降落

这是我们的枚举，算是排列型枚举，我们根据某架飞机能不能降落来做剪枝

#include <iostream>
#include <cstring>
using namespace std;
const int N = 15;
int st[N];
int t[N],d[N],l[N];
int n;
bool dfs(int pos,int end)
{if(pos == n){return true;}for(int i = 1;i<=n;i++){if(t[i]+d[i] < end) continue;if(st[i] == 1) continue;st[i] = 1;int newend = max(t[i],end)+l[i];if(dfs(pos+1,newend)) return true;st[i] = 0;}return false;
}
int main()
{int T;cin >> T;while(T--){cin >> n;memset(st,0,sizeof (st));for(int i = 1;i<=n;i++){cin >> t[i] >> d[i] >> l[i];}if(dfs(0,0)){cout << "YES" << endl;}else{cout << "NO" << endl;}} return 0;
}