懒得写dfs的可以用next_permutation
查看原帖
懒得写dfs的可以用next_permutation
396748
apxitye楼主2024/3/28 11:07
#include<bits/stdc++.h>
#define int long long
#define lfor(i,num,n) for(int (i)=(num);(i)<=(n);(i)++)
#define rfor(i,n,num) for(int (i)=(n);(i)>=(num);(i)--)
#define pb push_back
#define pii pair<int,int>
#define fst first
#define sec second
#define sz(a) (int)a.size()
#define read(a,n) vector<int> a(n+10); lfor(i,1,n) cin>>a[i];
#define putout(a,n) lfor(i,1,n) cout<<a[i]<<' ';cout<<endl;
#define c3(a,b,c) cout<<a<<' '<<b<<' '<<c<<endl;
using namespace std;
const int maxn=2e5+10,mod=1e9+7,INF=1e18;
struct plane{
    int t,d,l;
    int id;
};

bool cmp(plane a,plane b){
    return a.id<b.id;
}

void solve(){
    int n;cin>>n;
    vector<plane> a(n+10);
    lfor(i,1,n){
        cin>>a[i].t>>a[i].d>>a[i].l;
        a[i].d+=a[i].t;
        a[i].id = i;
    }
    int g[12];
    auto check=[&](){
        int f=0;
        lfor(j,1,n){
            int i = g[j];
            if(a[i].d<f){
                return false;
            }
            else{
                f=max(f+a[i].l,a[i].t+a[i].l);
            }
        }
        return true;
    };
    lfor(i,1,n) g[i] = i;
    do{
        if(check()){
            cout<<"YES"<<endl;
            return;
        }
    }while(next_permutation(g+1,g+1+n));
    cout<<"NO"<<endl;
}


signed main(){
    ios::sync_with_stdio(false);
    int T;cin>>T;
    while(T--) solve();
    return 0;
}
2024/3/28 11:07
加载中...