题目

问题描述
N 架飞机准备降落到某个只有一条跑道的机场。其中第 i 架飞机在 Ti 时刻到达机场上空，到达时它的剩余油料还可以继续盘旋 Di 个单位时间，即它最早可以于 Ti 时刻开始降落，最晚可以于 Ti + Di 时刻开始降落。降落过程需要 Li 个单位时间。

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

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

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

输出格式
对于每组数据，输出 YES 或者 NO，代表是否可以全部安全降落。

思路

• 题目问所有飞机是否可以安全降落，即是否存在一个飞机降落顺序的合理方案，那么就要考虑飞机降落的先后顺序问题，结合数据范围，可以使用DFS进行暴力搜索，判断所有的飞机排列是否存在合法方案。

• 搜索的是“坑位”：即第u个降落的飞机可以是任意未降落的飞机（只要满足时间约束）。

• 遍历所有可能的排列：由于 for(int i = 0; i < n; i++) 会尝试所有未访问的飞机，所以实际上是在枚举所有可能的降落顺序（排列）！

• 具体的条件性质需要推导出来。t``d``l之间的关系应用。

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

const int N = 15;
int t,n;
struct Plane
{
  int t,d,l;
};
Plane p[N];
bool sta; //记录是否可以全部安全降落
bool vis[N]; //记录飞机是否成功降落

//时间是按照时间轴进行比较的，不是单纯的持续时间
void dfs(int u, int last) //填的第几个坑位、上一架飞机降落完毕的时间
{
  if(u == n) //坑位填完
  {
    sta = true;
    return ;
  }
  for(int i = 0; i < n; i ++) //注意这里是从0开始，每一个飞机都有可能进行填坑！（只要是还没有降落）
  {
    if(vis[i] == false &&  (p[i].t+p[i].d) >= last) 
    //这个飞机最晚开始降落的时间>=上一架飞机降落的时间，那么就可以安全降落
    {
      vis[i] = true;
      dfs(u+1, max(last, p[i].t) + p[i].l);  //遍历的是坑位而不是飞机的序号，因为是无序进行起飞
      //1本架飞机降落要在上一架飞机降落之后
      //2并且本架飞机降落要在本架飞机到达之后

      vis[i] = false; //恢复现状
    }
  }
}

int main()
{
  scanf("%d",&t);
  while(t --)
  {
    scanf("%d",&n);
    for(int i = 0; i < n; i ++)
    {
      scanf("%d%d%d",&p[i].t,&p[i].d,&p[i].l); //每次输入都会覆盖
    }
    //重置状态
    memset(vis, 0, sizeof(vis));
    sta = false;

    dfs(0,0); //从第0号坑位开始填，初始上一个飞机降落时间默认last=0

    if(sta == true)
      printf("YES\n");
    else
      printf("NO\n");
  }
  return 0;
}