建站宝盒开通,个人博客模板 wordpress,h5响应式网站设计方案,wordpress 主题 保存原题链接#xff1a;[蓝桥杯 2023 省 B] 飞机降落 - 洛谷
目录
1. 题目描述
2. 思路分析
3. 代码实现 1. 题目描述 2. 思路分析
dfs全排列的变形题。
因为最后问飞机是否降落#xff0c;并且一架飞机降落完毕时另一架飞机才能降落。所以我们设置dfs的两个变量cnt为安全…原题链接[蓝桥杯 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(cnt1,max(t[i],sum)l[i])之所以要取max就是如果当前飞机的降落时间t[i]比sum小就从上一架飞机降落的时间sum开始降落否则就以t[i]时间开始降落。
注意要回溯 3. 代码实现
#includebits/stdc.h
using namespace std;
#define int long long
#define endl \n
const int N20;
int n,t[N],d[N],l[N],f;
bool vis[N];void dfs(int cnt,int sum){if(cntn){f1; return;}for(int i1;in;i){if(!vis[i]t[i]d[i]sum){vis[i]true;dfs(cnt1,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(_--){cinn;for(int i1;in;i) vis[i]0;f0;for(int i1;in;i){cint[i]d[i]l[i];}dfs(0,0);if(f) coutYESendl;else coutNOendl;}return 0;
}
