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

本文主要是介绍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;
}