2023蓝桥杯C++省赛B组：飞机降落

题目链接https://www.dotcpp.com/oj/problem3151.html       

         每个飞机都可以在【T,  T + L】区间内降落，最晚可以在【T + D, T + L + D】区间内降落。

        降落需要花费 L 个时间，也就是说要在【T, T + D + L】这个区间选择一个长度为 L 的区间（可以自己在纸上画个图，就很清楚了）。

        总共 N 个飞机，所以我们需要在每架飞机各自的【T, T + D + L】 区间内选择出合适的长度为 L 的区间，使得这 N 个长度为 L 的区间互相不重叠，就可以降落，如果有重叠，就无法降落。

        

        因为题目数据范围很小，所以可以用DFS：

                记录两个状态：

                一是当前一共降落了几架飞机。

                二是上一架飞机降落完毕的时间点。

        对于上一架飞机，开始降落的时间点能早就早，但是不能比它自己的 “上一架” 的降落完毕的时间早

         

        代码如下：

        如果已经降落了10架飞机，就返回1，证明可以全部降落；

        否则需要找一架飞机，满足这样的条件：

                还没有降落：! book[i]

                最晚开始降落的时间比上一架飞机的降落完毕的时间要靠后：q[i].a + q[i].b >= last

#include<bits/stdc++.h>using namespace std;struct node {int a, b, c;}q[11];int t, n;bool book[11]; // 标记第 i 架飞机是否降落bool dfs(int num, int last) {if(num == n)return 1;for(int i = 1; i <= n; i++) {if(!book[i] && q[i].a + q[i].b >= last) {book[i] = 1;if(dfs(num + 1, max(last, q[i].a) + q[i].c))return 1;book[i] = 0;}}return 0;}int main() {cin >> t;while(t--) {memset(book, 0, sizeof(book)); // 不要忘记每组测试样例都恢复一下 book 数组的值cin >> n;for(int i = 1; i <= n; i++) {int a, b, c;cin >> a >> b >> c;q[i].a = a;q[i].b = b; q[i].c = c;}if(dfs(0, 0))cout << "YES\n";elsecout << "NO\n";}return 0;}

本文链接：https://www.kjpai.cn/news/2024-04-12/157773.html，文章来源：网络cs，作者：康由，版权归作者所有，如需转载请注明来源和作者，否则将追究法律责任！