UVA 103 Stacking Boxes - n 維箱子嵌套最長路徑 (DAG DP)

題目大意

給定 k ≤ 30 個 n ≤ 10 維箱子。箱子可任意重排維度 (即維度排序後逐維比較)。A 能嵌套進 B ⇔ 排序後 A[i] < B[i] 對所有 i 成立。求最長嵌套鏈 (最多箱子數) 並輸出任一最長鏈的箱子編號 (輸入順序 1-based)。

建模：DAG 最長路徑

• 節點：箱子 (已將各維度排序)。
• 有向邊 i → j：箱子 i 能嵌套進 j (sorted[i][d] < sorted[j][d] ∀d)。
• 目標：DAG 中最長路徑 (節點數最多)。

DP + DFS 遞歸備忘錄

int dp[MAXN]; // dp[u] = 以 u 為起點的最長路徑長度
int nxt[MAXN]; // 記錄下一節點用於重構路徑

int dfs(int u) {
    if (dp[u]) return dp[u];
    dp[u] = 1;
    for (int v = 0; v < k; ++v) if (u != v && can_nest(u, v)) {
        int len = dfs(v) + 1;
        if (len > dp[u]) {
            dp[u] = len;
            nxt[u] = v;
        }
    }
    return dp[u];
}

bool can_nest(int i, int j) {
    for (int d = 0; d < n; ++d)
        if (box[i][d] >= box[j][d]) return false;
    return true;
}

路徑重構與輸出

// 找全局最長起點
int best_len = 0, start = -1;
for (int i = 0; i < k; ++i)
    if (dfs(i) > best_len) { best_len = dfs(i); start = i; }

// 輸出路徑 (內層→外層)
for (int u = start; u != -1; u = nxt[u])
    cout << (u+1) << (nxt[u]==-1 ? '\n' : ' ');

完整流程

1. 讀入 k, n，多測資至 EOF。
2. 讀入 k 個箱子，各自 n 維，**每個箱子內部排序**。
3. 建圖 / 直接在 DFS 中 can_nest 判斷 (k≤30, 完全圖檢查 O(k²n) 微小)。
4. DFS DP 求最長路徑長度與路徑。
5. 輸出長度與路徑 (編號 1-based)。

複雜度

• 時間：O(k² n) 建圖/檢查 + O(k²) DP，k=30, n=10 極快。
• 空間：O(k²) 或 O(k) (DFS 遞歸棧)。

關鍵細節

• 箱子內部排序：嵌套判斷前提，將「任意重排維度」轉化為「排序後逐維比較」。
• 多測資處理：每案例重置 dp, nxt, box。
• 輸出格式：長度換行，路徑數字空格分隔換行。任一最長鏈皆可。