2023年第十四届蓝桥杯大赛软件类省赛C/C++大学B组真题-飞机降落

本文主要是介绍2023年第十四届蓝桥杯大赛软件类省赛C/C++大学B组真题-飞机降落，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

思路：根据数据范围N<=10猜测用DFS+剪枝，因为菜狗不会状压dp。根据题目，一般这种飞机的题都会用到贪心的思想。思想是每架飞机都要卡极限最早降落时间，从而保证后面的飞机能够有充足时间降落。
代码参考博客@MQy大佬有详细解答

#include <bits/stdc++.h>
using namespace std;
const int N = 10;
int n;
struct Plane {int t, d, l;
}p[N];bool vis[N];
bool dfs(int pos, int last){if(pos == n) return true;for(int i = 0; i < n; ++i){int t = p[i].t, d = p[i].d, l = p[i].l;if(!vis[i] && t + d >= last){vis[i] = true;if(dfs(pos + 1, max(last, t) + l)) return true;vis[i] = false;}}return false;
}int main(void){int T;cin >> T;while(T--){scanf("%d", &n);for(int i = 0; i < n; ++i){int t, d, l;scanf("%d%d%d", &t, &d, &l);p[i] = {t, d, l};}memset(vis, 0, sizeof vis);if(dfs(0,0)) puts("YES");else puts("NO");}return 0;
}

这篇关于2023年第十四届蓝桥杯大赛软件类省赛C/C++大学B组真题-飞机降落的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---