题目描述

有N架飞机准备降落到某个只有一条跑道的机场。其中第i架飞机在 Ti时刻到达机场上空，到达时它的剩余油料还可以继续盘旋Di个单位时间，即它最早可以于Ti时刻开始降落，最晚可以于Ti+Di时刻开始降落。降落过程需要Li个单位时间。
一架飞机降落完毕时，另一架飞机可以立即在同一时刻开始降落，但是不能在前一架飞机完成降落前开始降落。
请你判断N架飞机是否可以全部安全降落。

输入格式
输入包含多组数据。
第一行包含一个整数T，代表测试数据的组数。
对于每组数据，第一行包含一个整数 N。
以下N行，每行包含三个整数：Ti，Di和 Li。

输出格式
对于每组数据，输出 YES 或者 NO，代表是否可以全部安全降落。
数据范围：对于 30%的数据，N≤2。
对于 100%的数据，1≤T≤10，1≤N≤10，0≤Ti,Di,Li≤105。

样例

输入样例：
2
3
0 100 10
10 10 10
0 2 20
3
0 10 20
10 10 20
20 10 20
输出样例：
YES
NO

C++ 代码

#include <cstring>
#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;

const int N = 10;  // 定义常量N为10，表示飞机的最大数量
int n;  // 变量n表示当前飞机的数量

// 定义飞机的结构体，包括起飞时间t、飞行时长d、降落后的冷却时间l
struct Plane {
  int t, d, l;
} p[N];

bool st[N];  // 用于标记飞机是否被选择过

// 深度优先搜索函数，参数u表示当前处理的飞机编号，last表示上一架飞机的降落时间
bool dfs(int u, int last) {
  if (u == n)  // 若所有飞机都已处理完，则返回true
    return true;

  // 遍历所有飞机
  for (int i = 0; i < n; i++) {
    int t = p[i].t, d = p[i].d, l = p[i].l;

    // 判断当前飞机是否未被选择且满足降落条件
    if (!st[i] && t + d >= last) {
      st[i] = true;  // 标记当前飞机被选择

      // 递归调用dfs处理下一架飞机，更新last为当前飞机降落后的时间
      if (dfs(u + 1, max(last, t) + 1))
        return true;

      st[i] = false;  // 回溯，取消当前飞机的选择
    }
  }

  return false;  // 若无法安排所有飞机的降落，则返回false
}

int main() {
  int T;
  scanf("%d", &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(st, 0, sizeof st);  // 初始化标记数组为false

    // 调用dfs判断是否存在一种安排使得所有飞机都能成功降落
    if (dfs(0, 0))
      puts("YES");
    else
      puts("NO");
  }

  return 0;
}