P9241 [蓝桥杯 2023 省 B] 飞机降落

原题链接：[蓝桥杯 2023 省 B] 飞机降落 - 洛谷 

目录

1. 题目描述

2. 思路分析

3. 代码实现

1. 题目描述

2. 思路分析

dfs全排列的变形题。

因为最后问飞机是否降落，并且一架飞机降落完毕时另一架飞机才能降落。所以我们设置dfs的两个变量cnt为安全降落的飞机数量cnt和上一架飞机降落的时间sum。

设置一个vis[ ]数组表示当前飞机有没有被搜过，一个变量f表示所有飞机是否能安全降落，如果能f最后值为1，否则为0。 

dfs入口就写dfs(0,0），进行搜索即可。

当前飞机如果能安全降落，那么它最晚的降落时间（t[i]+d[i]，因为能盘旋在空中）必须大于等于上一架飞机降落的时间sum。也就是能往下搜的条件是首先飞机没有被搜过（!vis[i]），同时t[i]+d[i]>=sum （该飞机最晚降落时间大于等于上一架飞机降落时间）。

要搜下一架飞机时，这时候要dfs(cnt+1,max(t[i],sum)+l[i])，之所以要取max，就是如果当前飞机的降落时间t[i]比sum小，就从上一架飞机降落的时间sum开始降落，否则就以t[i]时间开始降落。

注意要回溯

3. 代码实现

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
const int N=20;
int n,t[N],d[N],l[N],f;
bool vis[N];

void dfs(int cnt,int sum){
    if(cnt==n){
        f=1; return;
    }
    for(int i=1;i<=n;i++){
        if(!vis[i]&&t[i]+d[i]>=sum){
            vis[i]=true;
            dfs(cnt+1,max(t[i],sum)+l[i]);
            vis[i]=false;
        }
    }
}

signed main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    int _; cin>>_;
    while(_--){
        cin>>n;
        for(int i=1;i<=n;i++) vis[i]=0;
        f=0;
        for(int i=1;i<=n;i++){
            cin>>t[i]>>d[i]>>l[i];
        }
        dfs(0,0);
        if(f) cout<<"YES"<<endl;
        else cout<<"NO"<<endl;
    }
    return 0;
}