蓝桥杯备考：真题之飞机降落（暴搜+小贪心）
我们最多有十架飞机，可以选择dfs暴力搜索，枚举每种情况
那么，我们降落的时候怎么确定新的起点也就是newend呢？
如果飞机飞到机场的时刻是大于原来的end的，我们就让ti+li作为newend
否则，我们就让end作为newend
也就是
这种情况就没法降落
这种情况就是从end直接开始降落
这种情况就是从ti开始降落
这是我们的枚举，算是排列型枚举，我们根据某架飞机能不能降落来做剪枝
#include <iostream>
#include <cstring>
using namespace std;
const int N = 15;
int st[N];
int t[N],d[N],l[N];
int n;
bool dfs(int pos,int end)
{
if(pos == n)
{
return true;
}
for(int i = 1;i<=n;i++)
{
if(t[i]+d[i] < end) continue;
if(st[i] == 1) continue;
st[i] = 1;
int newend = max(t[i],end)+l[i];
if(dfs(pos+1,newend)) return true;
st[i] = 0;
}
return false;
}
int main()
{
int T;cin >> T;
while(T--)
{
cin >> n;
memset(st,0,sizeof (st));
for(int i = 1;i<=n;i++)
{
cin >> t[i] >> d[i] >> l[i];
}
if(dfs(0,0))
{
cout << "YES" << endl;
}
else
{
cout << "NO" << endl;
}
}
return 0;
}