AcWing 4957. 飞机降落
原题链接
简单
//dfs深度优先搜索:
//全排列:对给定的数按照字典序进行排列
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
bool st[15],flag;//n的最大值是10,防止数组越界
int a[15][3],n,t;//二位数组存储数据
const int N=20;//多开防止越界
//dfs:全排列
void dfs(int u,int l)//上一架飞机降落完成的时间
{
if(u==n)//5架飞机全排列,第六架飞机到的时候输出,所以只能等于
{
printf("YES\n");
flag=true;//标记为true
return;//回溯
}
if(flag==true) return;//搜索结束
//搜索过程
for(int i=1;i<=n;i++)
{
if(!st[i])//没有用过的
{
if(a[i][1]<l) //天空停留的时间不满足
{
flag=false;
return;
}
st[i]=true;
if(l<a[i][0])//没有盘旋时间
{
dfs(u+1,a[i][0]+a[i][2]);//到达天空时间+降落时间
}
else dfs(u+1,l+a[i][2]);//三段时间都包括
st[i]=false;
}
}
return;//回溯
}
int main()
{
cin>>t;
while(t--)
{
cin>>n;
memset(st,0,sizeof st);
flag=false;
for(int i=1;i<=n;i++)
{
cin>>a[i][0]>>a[i][1]>>a[i][2];
a[i][1]+=a[i][0];//在天空停留的时间段
}
dfs(0,0);
if(flag==false) printf("NO\n");
}
return 0;
}