DFS $O(n! \times nT)$

枚举全排列，然后判断这个飞机能不能降落

#include <iostream>
#include <cstdio>
#include <cstring>

using namespace std;

const int N = 10;

struct Plane
{
    int t,d,l;
}p[N];
int T,n;
int st[N];  //每个飞机有没有降落过

bool dfs(int u,int last)    //已经降落多少架飞机，当前这架飞机最早何时可以降落
{
    if(u == n)  return true;

    //枚举这一次降落那一架飞机（这一位放那个数）
    for(int i = 0; i < n; i ++)
    {
        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()
{
    cin >> T;
    while(T -- )
    {
        cin >> n;
        for(int i = 0; i < n; i ++)
        {
            int t,d,l;
            cin >> t >> d >> l;
            p[i] = {t, d, l};
        }

        memset(st,0,sizeof st);

        if(dfs(0, 0)) puts("YES");
        else puts("NO");
    }
    return 0;
}

状态压缩DP

状态中的1表示这一架飞机已经降落

#include <iostream>
#include <cstring>

using namespace std;

const int N = 10, M = 1 << N, INF = 0x3f3f3f3f;

struct Plane
{
    int t,d,l;
}p[N];
int T,n;
int f[M];       //状态i的飞机降落的时间的最小值

int main()
{
    cin >> T;
    while(T --)
    {
        cin >> n;
        for(int i = 0; i < n; i ++)
        {
            int t,d,l;
            cin >> t >> d >> l;
            p[i] = {t, d, l};
        }

        memset(f, 0x3f, sizeof f);
        f[0] = 0;   //没有飞机降落的话就是0
        for(int i = 0; i < 1 << n; i ++)     //枚举状态
            for(int j = 0; j < n; j ++) //枚举每一位，是1代表这一架飞机降落了
            {
                int t = p[j].t, d = p[j].d, l = p[j].l;
                if(i >> j & 1)
                {
                    int last = f[i - (1 << j)];
                    if(last <= t + d)
                        f[i] = min(f[i], max(last, t) + l);
                }
            }

        if(f[(1 << n) - 1] == INF) puts("NO");
        else puts("YES");
    }
    return 0;
}