蓝桥杯2023年第十四届省赛真题-飞机降落 简单的dfs

解题思路:

注意事项:

参考代码:

#include"bits/stdc++.h"
using namespace std;
#define ll long long
struct f{
    ll t,d,l;
}a[15];
ll t,n,kk;
bool cmp(f x,f y){
    return x.t+x.d<y.t+y.d;
}
bool vis[15];
void dfs(ll x,ll y){
    if(y==n){
        kk=1;
        return;
    }
    for(ll i=1;i<=n;i++){
        if(x>a[i].t+a[i].d&&!vis[i])return;
    }
    for(ll i=1;i<=n;i++){
        if(!vis[i]&&x>=a[i].t){
            vis[i]=true;
            dfs(x+a[i].l,y+1);
            vis[i]=false;
        }
        if(!vis[i]&&x<a[i].t){
            vis[i]=true;
            dfs(a[i].t+a[i].l,y+1);//可以等飞机哦
            vis[i]=false;
        }
    }
}
int main(){
    cin>>t;
    while(t--){
        memset(vis,false,sizeof(vis));
        memset(a,0,sizeof(a));
        cin>>n;
        kk=0;
        for(ll i=1;i<=n;i++)cin>>a[i].t>>a[i].d>>a[i].l;
        dfs(0,0);
        if(kk)cout<<"YES"<<endl;
        else cout<<"NO"<<endl;
    }
    return 0;
}