飞机降落状压DP写法
作者:
hblovo
,
2024-04-03 11:43:21
,
所有人可见
,
阅读 8
#include<bits/stdc++.h>
using namespace std;
const int N = 10,M = 1<<N;
int n;
int f[M][N];//状态为i,最后一架降落的是j
int t[N],d[N],l[N];
int main()
{
int T;
cin>>T;
while (T--)
{
memset(f, 0x3f, sizeof f);
cin >> n;
for (int i = 0; i < n; i++) scanf("%d%d%d", &t[i], &d[i], &l[i]);
for(int i = 0;i<n;i++){
int st = 1 << i;
f[st][i] = t[i] + l[i];
}
for(int i = 0;i<M;i++)
{
for(int j = 0;j<n;j++)
{
if((i >> j & 1))//当前状态i,最后一架降落的是j,那第j位肯定要为1
{
for(int k = 0;k < n;k++)
{
if(((i - (1 << j)) >> k) & 1)//由谁转移过来
{
int time = f[i-(1 << j)][k];
//如果j可以在k之后进行降落
if(time <= t[j]) f[i][j] = min(f[i][j],t[j] + l[j]);
else if(time <= t[j] + d[j]) f[i][j] = min(f[i][j],time + l[j]);
else f[i][j] = min(f[i][j], 0x3f3f3f3f);
}
}
}
}
}
bool flag = false;
for(int i = 0;i<n;i++)//最后降落的是i
{
if(f[(1<<n)-1][i] != 0x3f3f3f3f)
flag = true;
}
if (flag) printf("YES\n");
else printf("NO\n");
}
}