题目描述
有N架飞机准备降落到某个只有一条跑道的机场。
其中第 i架飞机在 Ti时刻到达机场上空,到达时它的剩余油料还可以继续盘旋 Di个单位时间,即它最早可以于Ti时刻开始降落,最晚可以于Ti+Di时刻开始降落。
降落过程需要 Li个单位时间。
一架飞机降落完毕时,另一架飞机可以立即在同一时刻开始降落,但是不能在前一架飞机完成降落前开始降落。
请你判断 N架飞机是否可以全部安全降落。
样例
2
3
0 100 10
10 10 10
0 2 20
3
0 10 20
10 10 20
20 10 20
输出样例
YES
NO
Y总讲的dp状态压缩版本,这个状态的存储是一维的,每一个状态用二进制的十进制来表示,例如5的二进制为101,其意思是第零架和第二架飞机已经降落,第一架飞机还没有降落;
具体的分析在代码的注释中十分详细
C++ 代码
#include<iostream>
#include<cstring>
#include<iostream>
using namespace std;
/*
M表示一共有多少种飞机降落的状态,因为之后要求最小值,所以设置一个INF表示正无穷
*/
const int N=11,M=1<<N,INF=0x3f3f3f3f;
/*
f[i]表示所有可以转化为状态i的总方案数的所需要的最小时间
假如i为5,则其二进制表示为101,则其可以由001,100,转化而来
所以f(i)=f(i-(1<<j))+l,其中j表示为在目前i状态下哪一位是1的位数,l是第j架飞机的降落时间
例如i=111001,则j可以为0,3,4,5(所有1对应的位数)
*/
int f[M];
struct Plant
{
int t,d,l;
}p[N];
int main()
{
int t;
cin>>t;
while(t--)
{
int n;
cin>>n;
for(int i=0;i<n;i++)
{
int t,d,l;
cin>>t>>d>>l;
p[i]={t,d,l};
}
//别忘了每次初始化,因为有t组数据
memset(f,0x3f,sizeof f);
//f[0]=0,就是目前一架飞机都没有听的最小时间一定是0
f[0]=0;
//遍历每一种状态
for(int i=0;i<1<<n;i++)
{
//遍历i状态的每一位
for(int j=0;j<n;j++)
{
int t=p[j].t,d=p[j].d,l=p[j].l;
//如果i状态的第j位为1,表示i可以由i-(1<<j)转化而来;
//例如i为101,则i可以由001,100转化而来
if((i>>j)&1)
{
//判断方案是否合法,也就是前一种状态的降落的最小时间一定要比第j架飞机的最晚降落时间要早
if(f[i-(1<<j)]<=t+d)
//如果合法接下来就是取最小值
//对于max(f[i-(1<<j)],t),要使第j架飞机降落合法,其开始时间一定不能早于t,
//并且为了保证时间最小,
//第j架飞机一定又要最早降落,所以要求max(f[i-(1<<j)],t),之后再加上降落时间l
f[i]=min(f[i],max(f[i-(1<<j)],t)+l);
}
}
}
//最后判断一下f[(1<<n)-1]是否被更新到,也就是所有飞机都降落的
//方案是否被更新到
//假如n=5,(1<<n)-1就是11111,所以就是判断f[11111]是否被更新,
//也就是其是否存在合法方案数
if(f[(1<<n)-1]<INF)puts("YES");
else puts("NO");
}
return 0;
}