题目传送门
关键考察点:dfs
贪心
具体详解
反正自己是没看懂,没想出来,以下是y总思路整理
将整个题目进行抽象化,每一个飞机开始降落到降落完成的时间看作一个线段,线段位置如果相互不重叠,那么就说明全部降落。
由于数据范围很小,所以可以采用dfs/状态压缩
由于个人太菜了,因此就只学dfs方法
dfs+贪心
用dfs搜索排出每个线段的顺序,对于dfs搜索的每一次,判断排出来的顺序是否合法(即N家飞机的降落时间是否可以完整不重叠的排开)
验证
贪心
(个人猜测贪心的原因是想要尽可能都凑起来,凑到给定的一组数据的每架飞机都能实现降落,因此在代码中,对于下一次要开始的传过去的last,由该组t和上一组的last所决定)
比如说下面的一组数轴
下一个趋区间既可以选择1也可以选择2
假设说选择了2,如果将2移动到1的位置,整体数据依旧可以满足都降落,
因此: 如果这个数轴,放的很靠右,整个还能有解,则将其放在最左的位置依旧有解的话且还会是最优解(也就对应了代码t+d>=last
)
换种说法来说:对于该数组,如果想尽可能的满足条件成立的可能,那么就将每一个线段尽可能的放在前一个的最右边。
如果整个数无解,那么就是其中有一种情况,下一个区间与上一个区间始终有交集。
细节:
1.在每次dfs的时候,传过去的值都会改变
要传过去的为这一次降落完成的时间,传给下一组数据
改变的值为:降落完成的时间:与之关联的是当前出发的最早时刻(也就是上一架飞机的降落时间)与该飞机到达上空的最大值
原因:如果last>t
,那么得等上一个降落完了才能去让这一个降落,如果last<t
那么得等该组飞机来了才能降落。
因此需要取其最大值。
再加上降落时间L,即为这一次飞机降落完成的时间,传递给下一次dfs
2.在if中的t+d>=last
这个的作用主要是为了能够尽可能的算到这一组数据能够实现都降落,最晚的降落时间为t+d,分析样例会发现,只要是last< t+d,那么就能够保证说一定有解,这是最广最基本的情况的保证
c++代码
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N =20;
struct Plane{
int t,d,l;
}p[N];
bool st[N];
int n;
//last是上一架飞机完成降落的时间
bool dfs(int u,int last)
{
if(u==n)
{
return true;//如果到达了第n层,说明所有飞机都没问题,都能顺利枚举完
}
for(int i=0;i<n;i++)
{
//取出t,d,l
int t=p[i].t,d=p[i].d,l=p[i].l;
//如果当前飞机(层)还没有判断过,并且如果其最晚降落的时间在上一组完成降落的时间之后(这样哪怕说最早时间不满足,依旧能够满足最晚时间,飞机能够降落,贪心思想),则标注并且递归到下一层
if(!st[i]&&t+d>=last)
{
st[i]=true;
if(dfs(u+1,max(last,t)+l))
return true;//取最早降落时间与上一架飞机完成降落时间的最大值
st[i]=false;
}
}
return false;
}
int main()
{
int T;
scanf("%d",&T);
while(T--)
{
scanf("%d", &n);
for(int i=0;i<n;i++)
{
int t,d,l;
scanf("%d%d%d", &t, &d, &l);
p[i]={t,d,l};
}
memset(st, 0, sizeof st);//每每组数据dfs前都先清空下st数组
if(dfs(0,0))puts("YES");
else puts("NO");
}
return 0;
}