状态压缩DP

import java.io.*;
import java.util.*;
public class Main{
    static int N = 12;
    static int M = 1 << 12;
    static PII[] fly = new PII[N];
    static int[] f = new int[M];
    static int INF = 0x3f3f3f3f;
    static int n;
    public static void main(String[] args)throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine());
        for(int cases = 1; cases <= T; cases ++){
            n = Integer.parseInt(br.readLine());
            for(int i = 0; i < n; i ++){
                String[] s1 = br.readLine().split(" ");
                int t = Integer.parseInt(s1[0]);
                int d = Integer.parseInt(s1[1]);
                int l = Integer.parseInt(s1[2]);
                fly[i] = new PII(t, d, l);
            }
            Arrays.fill(f, INF);
            f[0] = 0;
            for(int i = 0; i < 1 << n; i ++){
                for(int j = 0; j < n; j ++){
                    if((i & 1 << j) == 0){
                        int t = fly[j].t;
                        int d = fly[j].d;
                        int l = fly[j].l;
                        if(t + d >= f[i]) f[i | 1 << j] = Math.min(f[i | 1 << j], Math.max(f[i], t) + l);
                    }
                }
            }
            if(f[(1 << n) - 1] != INF) System.out.println("YES");
            else System.out.println("NO");
        }
    }
}
class PII{
    int t;
    int d;
    int l;
    public PII(int t, int d, int l){
        this.t = t;
        this.d = d;
        this.l = l;
    }
}

DFS

import java.io.*;
import java.util.*;
public class Main{
    static int N = 12;
    static PII[] fly = new PII[N];
    static boolean[] st = new boolean[N];
    static int n;
    static boolean dfs(int u, int time){//u表示已经降落的飞机数,time表示上一架飞机落地的时间
        if(u == n) return true;
        for(int i = 1; i <= n; i ++){
            int t = fly[i].t;
            int d = fly[i].d;
            int l = fly[i].l;
            if(!st[i] && t + d >= time){
                st[i] = true;
                if(dfs(u + 1, Math.max(t, time) + l)) return true;
                st[i] = false;
            }
        }
        return false;
    }
    public static void main(String[] args)throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine());
        for(int cases = 1; cases <= T; cases ++){
            Arrays.fill(st, false);//把状态复原
            n = Integer.parseInt(br.readLine());
            for(int i = 1; i <= n; i ++){
                String[] s1 = br.readLine().split(" ");
                int t = Integer.parseInt(s1[0]);
                int d = Integer.parseInt(s1[1]);
                int l = Integer.parseInt(s1[2]);
                fly[i] = new PII(t, d, l);
            }
            if(dfs(0, 0)) System.out.println("YES");
            else System.out.println("NO");
        }
    }
}
class PII{
    int t;
    int d;
    int l;
    public PII(int t, int d, int l){
        this.t = t;
        this.d = d;
        this.l = l;
    }
}