题目描述

dfs

样例

#include <iostream>
#include<algorithm>
#include <cmath>
#include<cstring>
using namespace std;
const int N = 15;
typedef long long ll;
int n;
struct plane {
    int t, d, l;
}a[N];
bool vis[N];
bool dfs(int n, int pos, int count, ll result)
{
    if (count == n) {
        return true;
    }
    for (int i = 0; i < n; i++)
    {
        if (a[i].t + a[i].d >= result&&!vis[i]) {
            vis[i] = true;
            if(a[i].t<=result){
                if(dfs(n,i,count+1,result+a[i].l)){
                    return true;
                }
            }else if(a[i].t>result){
                if(dfs(n,i,count+1,a[i].t+a[i].l)){
                    return true;
                }
            }
            vis[i] = false;
        }
    }
    return false;
}
void solve()
{
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> a[i].t >> a[i].d >> a[i].l;
    }
    bool p = false;
    for (int i = 0; i < n; i++)
    {
        memset(vis, false, sizeof vis);
        vis[i] = true;
        if (dfs(n, i, 1, a[i].t + a[i].l)) {
            p = true;
            break;
        }
        vis[i] = false;
    }
    if (p) {
        cout << "YES" << endl;
    }
    else {
        cout << "NO" << endl;
    }
}
int main()
{
    int T;
    cin >> T;
    while (T--)
    {
        solve();
    }
    return 0;
}