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

#include <bits/stdc++.h>

using namespace std;

// 该题，因为数据范围很小，所以可以 把所有的排列情况列出来
// 然后 每列出 一个飞机，我们就判断下 该飞机是否 符合条件，能够降落。
/*
  这里的 判断条件 就跟 贪心有关系了。
  如果每个飞机 取极限情况，它开始降落的时间正好是上一个飞机降落结束的时间。
  依次这样排下去。最后如果 有解的话。我们就说 符合题目条件。

  并且，这个时候，如果你 挪动一个飞机稍微往后一点儿。在允许的情况下。
  是可以产生其它 解的！！！ 
  即：每个飞机 取极限情况，它开始降落的时间正好是上一个飞机降落结束的时间。
  是 所有解的极限情况，也就是最优解。只需要判断它 是否存在 就可以了。

 */


const int N = 10;

int n;
struct Plane {
    int t, d, l;
}p[N];
bool vis[N]; // 表示该飞机已经降落过

// pos 表示当前降落了几次, last 表示上一个飞机降落时的时间
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;
        // 我们最大允许 t + d 时刻降落
        // 所以我们只需要 t + d >= 上一个飞机降落时的时间就可以正常降落
        // 并且 我们这里一定要贪心思想！
        // 我们 极限的降落时间 = max(last, t) + l
        if(!vis[i] && t + d >= last){ 
            vis[i] = true; // 标记这个飞机, 已经被选过了

            // 然后我们再继续 选下一个飞机
            if(dfs(pos + 1, max(last, t) + l)) return true; 
            // 只要 我们接下来 有一个环节，是哪个飞机都选不了的。
            // 那么就会跳出 for 循环，走到 return false
            // 则 整体 就会 一直 跳出 递归的栈，返回 false
            // 但是如果 pos == n 了, 那么只要返回一个 true, 就会一直 返回 true
            // 自己可以 分析下, 实在分析不出来, 画递归图看看。

            // 跳出 递归的栈，然后 把之前递归入栈的 vis[i] = true 操作还原
            vis[i] = false; // 我们也称其为 回溯, 实际上就是让我们 以后的位置 还可以选择这架飞机。

        }
    }

    return false;
}


/*
  解读下, 我们当前飞机 在 贪心思想下的 极限降落时间
  last = max(last, t) + l

  首先我们要知道, 我们的 t 也就是在天上刚刚周旋的这个时刻 可能比较靠后。所以 即使 t + d >= last
  我们 也无法 选择 last 作为 降落的起始时刻。所以 我们应该 max(last, t) 取一下 最大值作为 起始时刻
  然后 降落的时刻 = 起始时刻 + 降落所需时间(l)

  最后得到：last = max(last, t) + l

 */


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};
        }

        // 别忘记，每次都需要把 vis 标记数组 清空！
        memset(vis, 0, sizeof vis);
        if(dfs(0,0)) puts("YES");
        else puts("NO");
    }

    return 0;
}