思路:灵茶山艾府的回溯三问
当前操作:第i架飞机能否降落,起飞和盘旋时间之和>上一架飞机降落的时间
子问题: >=i , 去除 (起飞和盘旋时间之和<上一架飞机降落的时间 )的状态
下一个子问题i+1 的操作 , 计算上一架飞机的降落时间 ,是否立即降落
#include<iostream>
using namespace std;
int T,n;
int t[15],f[15],l[15];
int tim[15];
int cnt;
bool used[15];
//当前操作:第i架飞机能否降落,起飞和盘旋时间之和>上一架飞机降落的时间
//子问题: >=i,去除 (起飞和盘旋时间之和<上一架飞机降落的时间 )的状态
// i+1 的操作 , 计算上一架飞机的降落时间 ,是否立即降落
void dfs(int i,int sp){
if(i>=n){
cnt=1;
cout<<"YES"<<endl;
return;
}
if(cnt) return;
for(int j=0;j<n;j++){
if(used[j]==false){
if(sp>tim[j]) return;
used[j]=true;
dfs(i+1,max(sp,t[j])+l[j]);
used[j]=false;
}
}
}
int main(){
ios::sync_with_stdio(false);
cin>>T;
while(T--){
cin>>n;
cnt=0;
for(int i=0;i<n;i++){
cin>>t[i]>>f[i]>>l[i];
tim[i]=t[i]+f[i];
}
dfs(0,0);
if(!cnt) cout<<"NO"<<endl;
}
return 0;
}