飞机降落状压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];
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))
{
for(int k = 0;k < n;k++)
{
if(((i - (1 << j)) >> k) & 1)
{
int time = f[i-(1 << 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++)
{
if(f[(1<<n)-1][i] != 0x3f3f3f3f)
flag = true;
}
if (flag) printf("YES\n");
else printf("NO\n");
}
}