题目描述
有 N
架飞机准备降落到某个只有一条跑道的机场。
其中第 i
架飞机在 Ti
时刻到达机场上空,到达时它的剩余油料还可以继续盘旋 Di
个单位时间,即它最早可以于 Ti
时刻开始降落,最晚可以于 Ti+Di
时刻开始降落。
降落过程需要 Li
个单位时间。
一架飞机降落完毕时,另一架飞机可以立即在同一时刻开始降落,但是不能在前一架飞机完成降落前开始降落。
请你判断 N
架飞机是否可以全部安全降落。
输入格式
输入包含多组数据。
第一行包含一个整数 T
,代表测试数据的组数。
对于每组数据,第一行包含一个整数 N
。
以下 N
行,每行包含三个整数:Ti
,Di
和 Li
。
输出格式
对于每组数据,输出 YES 或者 NO,代表是否可以全部安全降落。
数据范围
对于 30%
的数据,N≤2
。
对于 100%
的数据,1≤T≤10
,1≤N≤10
,0≤Ti,Di,Li≤105
。
样例
2
3
0 100 10
10 10 10
0 2 20
3
0 10 20
10 10 20
20 10 20
算法
动态规划
C++ 代码
#include <bits/stdc++.h>
using namespace std;
const int N = 11, M = 1 << N;
int f[M][N], T[N], D[N], L[N]; //f[i][j]存储当状态是i,第j架飞机最后降落时的时间
//状态i用二进制表示,0表示还没降落,1表示降落
int main()
{
int m;
scanf("%d", &m);
while(m --)
{
memset(f, -1, sizeof f); //储存成-1,用作判断是否合法
int n;
scanf("%d", &n);
for(int t = 0; t < n; t ++)
{
scanf("%d%d%d", &T[t], &D[t], &L[t]);
f[1 << t][t] = T[t] + L[t]; //初始化,只有一架飞机降落后的时间
}
for(int i = 0; i < 1 << n; i ++) //枚举所有状态
for(int j = 0; j < n; j ++) //枚举第1到第n架飞机
if((i >> j) & 1) //如果这架飞机状态是1
{
int t = i - (1 << j); //以j为最后一架飞机
for(int k = 0; k < n; k ++) //枚举k,为倒数第二架(类似于哈密顿)
{
if((t >> k) & 1 && f[t][k] <= D[j] + T[j] && f[t][k] != -1) //判断是否合法
{
if(f[t][k] >= T[j])f[i][j] = f[t][k] + L[j]; //比最后一架飞机起始时间长就直接加L
else f[i][j] = T[j] + L[j]; //否则就是这架飞机的降落时间
}
}
}
bool jud = true; //判断是否输出"YES"
for(int t = 0; t < n; t ++)
if(f[(1 << n) - 1][t] >= 0)
{
puts("YES");
jud = false;
break;
}
if(jud)puts("NO");
}
return 0;
}