22软工孟姿好

用户名：dotcpp0669285

访问量：670

签　名：

莫道桑榆晚，为霞尚满天

等　　级
排　　名	1043
经　　验	3288
参赛次数	12
文章发表	41
年　　龄	20
在职情况	学生
学　　校	bilibili大学
专　　业	软件工程

　　自我简介：

自强不息

TA的其他文章

旧物有情 # 枚举法求素数
浏览：17

旧物有情 # 枚举法求水仙花数
浏览：13

旧物有情 # 遍历求二维数组转置
浏览：8

你可能喜欢

DFS+贪心 #3151: 蓝桥杯2023年第十四届省赛真题-飞机降落(C++)

　　作者: 22软工孟姿好　　　　发表时间：2024-11-22 09:34:55 浏览：4　|　评论：0　

原题链接：蓝桥杯2023年第十四届省赛真题-飞机降落

思路 : DFS + 贪心

DFS : 我们要找到一个排列,使得在该排列下,所有飞机能够安全降落
贪心 : 需要思考下一架飞机的最早降落时间,
		 飞机降落的越早越好,这样才能给后面的飞机留下更多容错
```
#define _CRT_SECURE_NO_WARNINGS 1
#include<algorithm>
#include<iostream>
#include<sstream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<string>
#include<vector>
#include<stack>
#include<queue>
#include<map>
#include<set>
#define MAX 0x3f3f3f3f
#define MIN -0x3f3f3f3f
using namespace std;
typedef long long ll;

const int N = 10;

bool used[N];

struct plane {
	int t, d, l;
}a[N];

int t, n;

//last:上一家飞机降落完毕的时间
//u : 当前第u架飞机是否降落
//这里的dfs的含义是,当前飞机是否能安全降落
//当u==n的时候,代表n架飞机全部安全降落
bool dfs(int u, int last) {
	if (u == n) return true;
	
	for (int i = 0; i < n; i++) {
		int t = a[i].t;
		int d = a[i].d;
		int l = a[i].l;

if (!used[i] && t + d >= last) {
			used[i] = true;
			//当前飞机有可能来的比上一架飞机降落时间早
			//也有可能上一家飞机降落完毕之后还没来
			//我们要考虑其最早的降落时间
			if (dfs(u + 1, max(last, t) + l))return true;
			used[i] = false;
		}
	}

return false;
}

int main() {
	cin >> t;
	while (t--) {
		cin >> n;
		int t, d, l;
		for (int i = 0; i < n; i++) {
			cin >> t >> d >> l;
			a[i] = { t,d,l };
		}
		//多组数据要注意初始化数组
		memset(used, false, sizeof used);
		if (dfs(0, 0))puts("YES");
		else puts("NO");
	}

return 0;
}
```

0.0分

0 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

22软工孟姿好

TA的其他文章

你可能喜欢

数据结构-有序线性表的有序合并（C语言代码）

C语言程序设计教程（第三版）课后习题7.4 （C语言代码）

C二级辅导-分段函数（C语言代码）

C语言训练-排序问题<1> （C语言代码）

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

DFS+贪心 #3151: 蓝桥杯2023年第十四届省赛真题-飞机降落(C++)

评论区

精彩推荐

C语言程序设计教程（第三版）课后习题6.1 （C语言代码）

C语言程序设计教程（第三版）课后习题6.1 （C语言代码）

简单的a+b （C语言代码）

C语言程序设计教程（第三版）课后习题8.3 （C语言代码）

C语言程序设计教程（第三版）课后习题3.7 （C语言代码）

C语言程序设计教程（第三版）课后习题8.8 （C语言代码）

C语言程序设计教程（第三版）课后习题5.4 （C语言代码）

【亲和数】（C语言代码）

一元一次方程（C语言代码）

单词个数统计（C语言代码）

22软工孟姿好

TA的其他文章

你可能喜欢

数据结构-有序线性表的有序合并 （C语言代码）

C语言程序设计教程（第三版）课后习题7.4 （C语言代码）

C二级辅导-分段函数 （C语言代码）

C语言训练-排序问题<1> （C语言代码）

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

DFS+贪心 #3151: 蓝桥杯2023年第十四届省赛真题-飞机降落(C++)

评论区

精彩推荐

C语言程序设计教程（第三版）课后习题6.1 （C语言代码）

C语言程序设计教程（第三版）课后习题6.1 （C语言代码）

简单的a+b （C语言代码）

C语言程序设计教程（第三版）课后习题8.3 （C语言代码）

C语言程序设计教程（第三版）课后习题3.7 （C语言代码）

C语言程序设计教程（第三版）课后习题8.8 （C语言代码）

C语言程序设计教程（第三版）课后习题5.4 （C语言代码）

【亲和数】 （C语言代码）

一元一次方程 （C语言代码）

单词个数统计 （C语言代码）

数据结构-有序线性表的有序合并（C语言代码）

C二级辅导-分段函数（C语言代码）

　　评论区

【亲和数】（C语言代码）

一元一次方程（C语言代码）

单词个数统计（C语言代码）