dfs+剪枝,很清晰的的思路,小白一遍懂
看完那你也觉得这题很一般呀!!!
算法
C++ 代码
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 15;
struct nade
{
int start; //(飞机到达时间)
int end; // 飞机能降落的最后时间(Ti + Di)
int spend; // 飞机降落花费的时间
bool flag; // 用来判断飞机是否降落
}w[N];
int n,t;
bool cmp(nade a,nade b){
return a.start<b.start;
}
bool dfs(int num,int tim) //num是飞机已经降落的个数,tim是现在的时刻
{
if(num == n) return true; //如果飞机都降落,返回真
for(int i=0;i<n;i++){ //从第一个到达的飞机开始遍历
if(!w[i].flag && w[i].end>=tim){ //如果飞机没降落,且现在的时刻在飞机能降落的最后时间之前,将飞机降落
w[i].flag = true;
if(dfs(num+1,max(tim,w[i].start)+w[i].spend)) return true;//存在现在时刻飞机还没到的情况,所以需要使用max(tim,w[i].start)+w[i].spend)来确定这架飞机刚完成降落的时刻
//存在先到的飞机但是飞机能盘旋的时间较长,需要先让后面的飞机降落的情况
//所以需要回溯算法,此处先判断先让先到达的飞机降落,看看后续飞机能不能
//安全降落。如果能,就返回true,不能就先跳过这架飞机,先判断后到的飞机
w[i].flag = false; //先跳过这架飞机
}
}
return false;
}
int main()
{
scanf("%d",&t);
while(t--)
{
scanf("%d",&n);
for(int i=0;i<n;i++)
{
int a,b,c;
scanf("%d%d%d",&a,&b,&c);
w[i] = {a,a+b,c,false};//b为盘旋时间,a+b是能降落的最迟时间
}
sort(w,w+n,cmp); //飞机先来后到排序
if(dfs(0,0)) cout<<"YES"<<endl;
else cout<<"NO"<<endl;
}
return 0;
}