题目描述
类似于全排列问题!!!
本质就是看是否找到一种降落顺序使三架飞机都能平安降落
假设n为3,一共有3架飞机需要降落,看是否找到一种降落顺序使三架飞机都能平安降落。顺序:1,2,3; 1,3,2; 2,1,3; 2,3,1; 3,1,2; 3,2,1;
C++ 代码
#include<iostream>
#include<cmath>
#include<cstring>
using namespace std;
const int N=1e5+10;
int k,n;
int t[N],d[N],l[N];
int flag,vis[N];
void dfs(int cnt,int time){
if(flag) return;
if(cnt==n){
flag=true;
return;
}
for(int i=0;i<n;i++){
if(!vis[i] && t[i]+d[i]>=time){
vis[i]=1;
dfs(cnt+1,max(time,t[i])+l[i]);
vis[i]=0;
}
}
}
int main(){
cin>>k;
while(k--){
cin>>n;
for(int i=0;i<n;i++){
cin>>t[i]>>d[i]>>l[i];
}
//初始化
memset(vis,0,sizeof vis);
flag=0;
dfs(0,0);
if(flag){
cout<<"YES"<<endl;
}else{
cout<<"NO"<<endl;
}
}
return 0;
}