50 lines
1.1 KiB
C++
50 lines
1.1 KiB
C++
// lanqiao 3511 飞机降落
|
|
#include<bits/stdc++.h>
|
|
using namespace std;
|
|
const int N = 1e2 + 10;
|
|
struct node{
|
|
int t, d, l; // 分别代表可以降落的时刻，盘旋时间，降落花费时间
|
|
}a[N];
|
|
bool vis[N] = {false};
|
|
int t, n;
|
|
bool flag = false;
|
|
// lasttime: 之前完成降落的所有飞机中的最后一架飞机降落的时间
|
|
void dfs(int dep, int lasttime){
|
|
if(dep == n + 1){
|
|
flag = true;
|
|
return;
|
|
}
|
|
for(int i = 1; i <= n; i++){
|
|
if(!vis[i] && a[i].t + a[i].d >= lasttime){
|
|
vis[i] = true;
|
|
dfs(dep + 1, max(lasttime, a[i].t) + a[i].l);
|
|
// 遍历同级的另一个飞机的下一个深度的飞机前，需要将该飞机设置为未安排状态
|
|
vis[i] = false;
|
|
}
|
|
}
|
|
}
|
|
int main(){
|
|
cin >> t;
|
|
while(t--){
|
|
cin >> n;
|
|
for(int i = 1; i<=n; i++){
|
|
cin >> a[i].t >> a[i].d >> a[i].l;
|
|
}
|
|
flag = false; // 重置
|
|
dfs(1, 0);
|
|
if(flag) cout << "YES" << endl;
|
|
else cout << "NO" << endl;
|
|
}
|
|
return 0;
|
|
}
|
|
/* test samples
|
|
2
|
|
3
|
|
0 100 10
|
|
10 10 10
|
|
0 2 20
|
|
3
|
|
0 10 20
|
|
10 10 20
|
|
20 10 20
|
|
*/ |