蓝桥杯每日一题：飞机降落

题目来源：第十四届蓝桥杯大赛软件赛省赛B组

$N$ 架飞机准备降落到某个只有一条跑道的机场. 其中第$i$ 架飞机在$T_i$ 时刻到达机场上空, 到达时它的剩余油料还可以盘旋$D_i$ 个单位时间, 即它最早可以于$T_i$ 时刻降落, 最晚可以于$T_i + D_i$ 时刻降落. 降落过程需要$L_i$ 个单位时间

一架飞机降落完毕时, 另一架飞机可以立即在同一时刻开始降落, 但是不能在前一架飞机完成降落之前开始降落

请判断$N$ 架飞机是否可以全部安全降落

输入: 输入包含多组数据

第一行包含一个整数$T$ , 代表测试的组数

对于每组数据, 第一行包含一个整数$N$

以下$N$ 行, 每行包括三个整数:$T_i, D_i, L_i$

输出: 对于每组数据, 输出 YES 或者 NO, 代表是否可以全部安全降落

Input Sample:

2
3
0 100 10
10 10 10
0 2 20
3
0 10 20
10 10 20
20 10 20

Output Sample:

YES
NO

这道题数据范围特别小, 最多只有10架飞机, 因此可以直接DFS搜索.如果合法的话就输出"YES", 找不到合法方案就输出"NO"

下面给出题解. 请注重思考, 不要无脑cv

#include <bits/stdc++.h>
using namespace std;
struct plane {
	/* data */
	int s, e, l;
    // s 到达机场时间
    // e 最晚降落时间
    // l 降落时长
}a[11];
bool t[11];
int n;

void io() {
	cin.tie(0);
	cout.tie(0);
	ios::sync_with_stdio(false);
}
// dfs搜索, 因为数据量特别小, 所以完全不会tle
bool dfs(int i, int time, int cnt) {
	if (cnt == n) {
        // 正解, n架飞机均能降落
		return true;
	}
	bool flag = false;
	t[i] = true;
	time += a[i].l;
	for (int i = 1; i <= n; i++) {
		if (!t[i]) {
			int start = a[i].s, end = a[i].e;
			if (end < time) {
                // 如果当前时间已经比这架飞机的最晚降落时间还要晚, 那么这种情况是不合法的, 返回false
				flag = false;
				break;
			}
			flag |= dfs(i, max(start, time), cnt + 1);
			if (flag) {
				break;
			}
		}
	}
	t[i] = false;
	return flag;
}

void test() {
	cin >> n;
	for (int i = 1; i <= n; i++) {
		int t, d, l;
		cin >> t >> d >> l;
		a[i].s = t, a[i].e = t + d, a[i].l = l;
	}
	for (int i = 1; i <= n; i++) {
		if (dfs(i, a[i].s, 1)) {
			cout << "YES" << '\n';
			return;
		}
	}
	cout << "NO" << '\n';
}

int main() {
	io();
	int T;
	cin >> T;
	while (T--) {
		test();
	}
}