解題思路

這道題目要求我們判斷給定的飛機是否都能在它們的油料耗盡之前降落。為了尋找是否存在合法的降落序列，我們可以使用深度優先搜索（DFS）的方法，嘗試所有可能的降落順序。

首先，我們需要理解題目中的條件。每架飛機在 $T_i$ 時刻到達機場上空，剩余油料可以維持 $D_i$ 個單位時間，降落需要 $L_i$ 個單位時間。這意味著每架飛機可以在 $T_i$ 到 $T_i+D_i$ 的時間段內開始降落。

然后，我們可以按照以下步驟來實現 DFS：

1. 首先，我們初始化一個布爾數組 st[] 來記錄每架飛機是否已經降落。
2. 然后，我們對每架飛機嘗試進行降落。這里的 “嘗試” 意味著我們需要檢查該飛機是否可以在當前的時間內開始降落，即它的開始降落時間是否在 $T_i$ 到 $T_i+D_i$ 的時間段內。如果可以，我們就讓它降落，并把 st[i] 設置為 true。
3. 在一架飛機降落之后，我們遞歸地對剩下的飛機進行嘗試。這一步就是 DFS 的主要部分，我們需要在所有的可能的降落序列中進行搜索。
4. 如果在某一步我們發現當前的飛機無法在當前的時間內開始降落，我們就返回 false，并在上一層中嘗試下一架飛機。
5. 如果所有的飛機都已經降落，我們就返回 true。
6. 最后，我們對所有飛機進行嘗試。如果存在至少一個可以讓所有飛機都降落的序列，我們就輸出 YES，否則輸出 NO。

通過以上步驟，我們可以找出是否存在一個合法的降落序列，使得所有的飛機都能在它們的油料耗盡之前降落。

AC_Code

• C++

#include <iostream>
#include <cstring>
#include <algorithm>using namespace std;const int N = 15;int n;
int a[N], b[N], c[N];
bool st[N];bool dfs(int u, int last, int cnt)
{if (b[u] < last)return false;if (cnt == n)return true;for (int i = 0; i < n; ++ i )if (!st[i]){st[i] = true;if (dfs(i, max(a[u], last) + c[u], cnt + 1))return true;st[i] = false;}return false;
}int main()
{int T;cin >> T;while (T -- ){memset(st, 0, sizeof st);cin >> n;for (int i = 0; i < n; ++ i )cin >> a[i] >> b[i] >> c[i], b[i] += a[i];bool flag = false;for (int i = 0; i < n; ++ i ){st[i] = true;if (dfs(i, 0, 1)){flag = true;break;}st[i] = false;}cout << (flag? "YES": "NO") << endl;}return 0;
}

• Java

import java.util.*;public class Main {static final int N = 15;static int n;static int[] a = new int[N], b = new int[N], c = new int[N];static boolean[] st = new boolean[N];static boolean dfs(int u, int last, int cnt) {if (b[u] < last) {return false;}if (cnt == n) {return true;}for (int i = 0; i < n; ++i) {if (!st[i]) {st[i] = true;if (dfs(i, Math.max(a[u], last) + c[u], cnt + 1)) {return true;}st[i] = false;}}return false;}public static void main(String[] args) {Scanner scanner = new Scanner(System.in);int T = scanner.nextInt();while (T-- > 0) {Arrays.fill(st, false);n = scanner.nextInt();for (int i = 0; i < n; ++i) {a[i] = scanner.nextInt();b[i] = scanner.nextInt() + a[i];c[i] = scanner.nextInt();}boolean flag = false;for (int i = 0; i < n; ++i) {st[i] = true;if (dfs(i, 0, 1)) {flag = true;break;}st[i] = false;}System.out.println(flag ? "YES" : "NO");}scanner.close();}
}

• Python

N = 15
a, b, c = [0]*N, [0]*N, [0]*N
st = [False]*Ndef dfs(u, last, cnt):if b[u] < last:return Falseif cnt == n:return Truefor i in range(n):if not st[i]:st[i] = Trueif dfs(i, max(a[u], last) + c[u], cnt + 1):return Truest[i] = Falsereturn FalseT = int(input().strip())
for _ in range(T):st = [False]*Nn = int(input().strip())for i in range(n):a[i], b[i], c[i] = map(int, input().strip().split())b[i] += a[i]flag = Falsefor i in range(n):st[i] = Trueif dfs(i, 0, 1):flag = Truebreakst[i] = Falseprint("YES" if flag else "NO")

【在線測評】