蓝桥杯2023年第十四届省赛真题-飞机降落(dfs)

#include <bits/stdc++.h>
using namespace std;
const int N = 20;
 
int vis[N];
int flag = 0;
int k;
int Time;
 
struct node {
    int T, D, L;
} mp[N];
 

void dfs(int x,int last) {
 
    if (x == k + 1) {
        flag = 1;
        return;
    }
 
    for (int i = 1; i <= k; i++) {
        if(flag)    
               return;
        if (x == 1)
            Time = mp[i].T;
 
        if (vis[i])
            continue;
 
        if (mp[i].T > Time)      
            Time += (mp[i].T - Time);
             
        if (mp[i].T + mp[i].D < Time)
            continue;
 
        vis[i] = 1;
        Time += mp[i].L;
         
        dfs(x + 1,Time);
         
        vis[i] = 0;
        if(mp[i].T>last) 
            Time-=(mp[i].T-last);
        Time -= mp[i].L;
 
    }
}
 
int main() {
 
    int n;
    cin >> n;
    while (n--) {
        memset(vis, 0, sizeof vis);
        memset(mp, 0, sizeof mp);
        flag = 0;
        cin >> k;
        for (int i = 1; i <= k; i++)
            cin >> mp[i].T >> mp[i].D >> mp[i].L;
        
        dfs(1,0);
        
        if (flag)
            cout << "YES" << endl;
        else
            cout << "NO" << endl;
    }
}