題目描述
N 架飛機準備降落到某個只有一條跑道的機場。其中第 i 架飛機在 Ti 時刻到達機場上空，到達時它的剩余油料還可以繼續盤旋 Di 個單位時間，即它最早可以于 Ti 時刻開始降落，最晚可以于 Ti + Di 時刻開始降落。降落過程需要 Li個單位時間。
一架飛機降落完畢時，另一架飛機可以立即在同一時刻開始降落，但是不能在前一架飛機完成降落前開始降落。
請你判斷 N 架飛機是否可以全部安全降落。
輸入格式
輸入包含多組數據。
第一行包含一個整數 T，代表測試數據的組數。
對于每組數據，第一行包含一個整數 N。
以下 N 行，每行包含三個整數：Ti，Di 和 Li。
輸出格式
對于每組數據，輸出 YES 或者 NO，代表是否可以全部安全降落。
樣例輸入
2
3
0 100 10
10 10 10
0 2 20
3
0 10 20
10 10 20
20 10 20
樣例輸出
YES
NO
提示
對于第一組數據，可以安排第 3 架飛機于 0 時刻開始降落，20 時刻完成降落。安排第 2 架飛機于 20 時刻開始降落，30 時刻完成降落。安排第 1 架飛機于 30 時刻開始降落，40 時刻完成降落。
對于第二組數據，無論如何安排，都會有飛機不能及時降落。
對于 30% 的數據，N ≤ 2。
對于 100% 的數據，1 ≤ T ≤ 10，1 ≤ N ≤ 10，0 ≤ Ti , Di , Li ≤ 105。

import java.util.*;  public class Main {  static final int N = 10;  static boolean[] st = new boolean[N];  static int n;  static boolean flag = false;  static int[] t = new int[N];  static int[] d = new int[N];  static int[] l = new int[N];  static void dfs(int u, int last) {  if (flag) return; // If we found one valid sequence, return  if (u == n) { // All planes have landed  flag = true;  return;  }  for (int i = 0; i < n; i++) {  if (!st[i]) { // If the current plane hasn't landed yet  if (t[i] + d[i] >= last) { // Check if it can wait for the last plane to land  st[i] = true; // Mark the plane as landed  if (t[i] > last) { // If this plane arrives after the last one has landed  dfs(u + 1, t[i] + l[i]); // Update last to arrival + landing time  } else { // If this plane arrives before or when the last one is landing  dfs(u + 1, last + l[i]); // Wait for the last plane to land  }  st[i] = false; // Backtrack  } else {  return; // If it can't wait, return  }  }  }  }  public static void main(String[] args) {  Scanner scanner = new Scanner(System.in);  int T = scanner.nextInt();  while (T-- > 0) {  n = scanner.nextInt();  for (int i = 0; i < n; i++) {  t[i] = scanner.nextInt();  d[i] = scanner.nextInt();  l[i] = scanner.nextInt();  }  for (int i = 0; i < N; i++) {  st[i] = false; // Reset the landing status  }  flag = false; // Reset the flag  dfs(0, 0); // Start DFS  if (flag) {  System.out.println("YES");  } else {  System.out.println("NO");  }  }  }  
}

import java.util.*;public class Main {static boolean flag=false;static boolean[] st;static int n;static Map<Integer,int[]> map;//static Scanner cin = new Scanner(System.in);public static void main(String[] args){int t= cin.nextInt();while(t--!=0)solve();}private static void solve() {n= cin.nextInt();flag=false;//標記，如果為true則搜素到答案st=new boolean[n];//初始胡標記數組，標記數組用于查詢未安排下降的飛機，如果標記數組全為true，則代表能成功全部安排map=new HashMap<>();for (int i = 0; i < n; i++) {//輸入int t= cin.nextInt();int d= cin.nextInt();int l= cin.nextInt();map.put(i,new int[]{t,d,l});}for (int i=0;i<n;i++){//枚舉第一架飛機安排st[i]=true;//標記搜索dfs(map.get(i)[0]+map.get(i)[2]);//搜索下一駕飛機應該安排什么，并把時間傳入下一個dfs，時間為飛機起飛時間加下降時間st[i]=false;//還原，取消標記}if(flag) System.out.println("YES");if(!flag) System.out.println("NO");}private static void dfs(int time) {boolean ok=true;//下面for循環中，如果沒有再安排飛機，則代表已經成功安排所有飛機for (int i=0;i<n;i++){//枚舉飛機if(st[i])continue;//如果已經下降了，不用再安排下降ok=false;if(time>map.get(i)[0]+map.get(i)[1])continue;int is=Math.max(time,map.get(i)[0])+map.get(i)[2];//時間取當前時間和飛機起飛時間最大那個，加上飛機下降時間st[i]=true;//標記dfs(is);//搜索下一駕飛機st[i]=false;//還原標記}if(ok)//代表搜素到答案 直接返回flag=true;return;}
}