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

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

解题思路

考虑直接暴力的话,时间复杂度为 \(O(n!×n×t)\) 。

首先，选择出这 \(n\) 架飞机的降落顺序，再按照题目模拟，能降就降。

如果已经判断出来可以，那么在后面的 \(DFS\) 中直接退出即可。

在已经判断判断出可以降落时，要注意上一架飞机降落时间是否是小于当前飞机到达时间

DFS过程：

首先设立一个为变量 \(k\) ，代表是否可以全部安全降落。即当 \(k\) 是 $true $ 时，输出 \(YES\)；\(k\) 是 \(false\) 时，输出 \(NO\)。 再设立一个变量 \(used\)，对于每一个 \(used_i\) ，表示第 \(i\) 架飞机是否已经降落。

设立一个状态，包含 \(dep\) 和 \(lst\) ，分别对应此时递归的步数和当前的时间。

对于每一个状态，枚举 \(n\) 次，若此时 \(T_i + D_i < lst\) ，即存在更好的方案，就 \(return\)。

若此时 \(T_i + D_i < lst\)且 \(used_i = 1\) ，就将 \(used_i\) 设为1，再通过这个状态转移下去，转移式：\(dfs(dep+1,max(T_i,lst)+L_i)\) 。

在每一个 \(dfs\) 开始前，先判断 \(dep\) 是否大于 \(n\)。若大于 \(n\) ，就将 \(k\) 设为1。

注意：转移结束后记得重置 \(used_i\) 。

参考代码

#include <bits/stdc++.h>
#define ll long long
#define endl '\n'
using namespace std;
const int MAXN=10+5;
int n;
int t[MAXN];
int d[MAXN];
int l[MAXN];
int start[MAXN], end[MAXN];
int used[MAXN];
int last=-1;
bool k=0;
int dfs(int dep,int lst){
    if(dep>n){
        k=1;
        return 0;
    }
    if(k)return 0;
    for(int i=1;i<=n;i++){
        if(!used[i]){
            if (t[i]+d[i]<lst) eturn 0;
            used[i]=1;
            dfs(dep+1,max(t[i],lst)+l[i]);
            used[i]=0;
        }
    }
    return 0;
}
int main(){
	int T;
    cin>>T;
    while(T--){
        k=0;
        memset(used,0,sizeof used);
        cin>>n;
        for(int i=1;i<=n;i++)
            cin>>t[i]>>d[i]>>l[i];
        dfs(1,-1);
        if (k)cout<<"YES"<<endl;
		else cout<<"NO"<<endl;
    }
}