AcWing 4957. 飞机降落
原题链接
简单
作者:
stc
,
2024-02-29 00:43:42
,
所有人可见
,
阅读 24
// 开始[T,T+D]
// 结束[T+L,T+D+L]
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 20;
int T,n;
struct Node{
int t,d,l;
}g[N];
bool st[N];
bool dfs(int u,int tm){
// 1.终止条件
if(u>n) return true;
for(int i=1;i<=n;i++){
if(!st[i]){
int now_tm = max(tm,g[i].t); // 此时开始降落的时间
// 此时开始降落的时间晚于要求
if(now_tm>g[i].t+g[i].d) return false;
st[i] = true;
now_tm = now_tm + g[i].l;
if(dfs(u+1,now_tm)) return true;
// 恢复现场
st[i] = false;
}
}
return false;
}
int main(){
cin>>T;
while(T--){
cin>>n;
// 别忘了每次初始化st
memset(st,0,sizeof st);
for(int i=1;i<=n;i++){
int t,d,l;
cin>>t>>d>>l;
g[i] = {t,d,l};
}
bool f = dfs(1,0);
cout<<(f?"YES":"NO")<<endl;
}
return 0;
}