题目描述

常规dfs
没看过排序数字的，可以先看排序数字：
链接： https://www.acwing.com/solution/content/232844/

样例

import java.util.*;
public class Main{
    static int T,n;

    static class p{
        int t,d,l;
        p(int t , int d , int l){
            this.t = t;
            this.d = d;
            this.l = l;
        }
    }

    static ArrayList<p> pp = new ArrayList<>();

    //判断当前飞机可不可以降落
    static boolean[] st = new boolean[12];

    //u代表当前降落了几架飞机 last代表上一架飞机降落的时间
    static boolean dfs(int u, int last){
        //如果u==n 说明全部飞机都能降落 返回true
        if(u == n)  return true;

        for(int i = 0 ; i < n ; i++){
            int t = pp.get(i).t;
            int d = pp.get(i).d;
            int l = pp.get(i).l;

            //如果当前飞机没有降落 且最晚降落时间t+d 大于等于 上一架飞机降落的时间
            if (!st[i] && t + d >= last)
            {
              //这架飞机可以降落
              st[i] = true;
              //走到下一架飞机，当前飞机降落的时间应该为上一架飞机降落的时间 + 自己降落所需的时间
              if (dfs(u + 1, Math.max(last, t) + l)) return true;
              //恢复现场 
              st[i] = false;
            }

        }

        return false;

    }

    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        T = sc.nextInt();
        while(T > 0){
            n = sc.nextInt();
            for(int i = 0 ; i < n ; i++){
                pp.add(new p(sc.nextInt(),sc.nextInt(),sc.nextInt()));
            }

            Arrays.fill(st,false);

            if(dfs(0,0)){
                System.out.println("YES");
            }else{
               System.out.println("NO");
            }

            pp.clear();

            T--;
        }
    }
}