第十四届蓝桥杯：DFS之飞机降落
这道题，由于它的数据范围是非常小的，我们可以采取暴力搜索的措施，把每种情况都枚举出来，如果有能行的情况就返回true
同时我们也要学会剪枝，如果已经确认飞机不能降落，就不要往下再展开了
#include <iostream>
#include <vector>
#include <cstring>
const int N = 30;
using namespace std;
int st[N];
int t[N],d[N],l[N];
int n,T;
bool dfs(int pos,int end)
{
if(pos>n)
{
return true;
}
for(int i = 1;i<=n;i++)
{
if(st[i]) continue;
if(end > t[i]+d[i]) continue;
int newend = max(end,t[i])+l[i];
st[i] = true;
if(dfs(pos+1,newend)) return true;
st[i] = false;
}
return false;
}
int main()
{
cin >> T;
while(T--)
{
memset(st,0,sizeof(st));
cin >> n;
for(int i = 1;i<=n;i++)
{
cin >> t[i] >> d[i] >> l[i];
}
if(dfs(1,0)) cout << "YES" << endl;
else cout << "NO" << endl;
}
return 0;
}