dfs+暴搜+剪枝

#include<iostream>
#include<cstring>
#include<algorithm>

using namespace std;

const int N=11;
int n,T;

bool st[N];//用来表示当前的飞机是否使用过

struct Plane{
    int t,d,l;
}plane[N];

bool dfs(int x, int last)//x表示当前第几架飞机准备降落，last表示上一个飞机的降落时间
{
    if(x == n) return true;//dfs第一步永远是判断true的情况，也就是边界条件
    //接下来模拟是否能找到一架飞机能够满足降落的条件
    for(int i=0;i<n;i++)
    {
        int t=plane[i].t;
        int d=plane[i].d;
        int l=plane[i].l;
        if(!st[i] && t+d >= last)//判断我当前飞机是否被使用过和是否可以降落
        {
            st[i]=1;//表示当前飞机已经使用了
            if(dfs(x+1, max(t,last) + l) == 1) return true;
            st[i]=0;//恢复现场
        }
    }
    //如果全部方案都没有找到，就直接返回false，表示当前这个飞机后面不可能再有满足的飞机能够降落
    return false;
}

int main()
{
    cin>>T;
    while(T--)
    {
        cin>>n;
        for(int i=0;i<n;i++) st[i]=0;//每次判断完一组数据之后要把st数组清0，确保不要影响到下一组数据
        for(int i=0;i<n;i++)
        {
            cin>>plane[i].t>>plane[i].d>>plane[i].l;
        }
        if(dfs(0,0) == true) cout<<"YES"<<endl;
        else  cout<<"NO"<<endl;
    }
    return 0;
}