題目的難度顏色使用 Luogu 上的分級，由簡單到困難分別為 🔴🟠🟡🟢🔵🟣⚫。

🔗 P2196 [NOIP 1996 提高组] 挖地雷

Problem Statement

題目簡述

有 $n$ 個地窖，每個地窖中有若干地雷。部分編號較小的地窖可以通往編號較大的地窖，形成一張只往後走的有向圖。可以從任意地窖開始，沿著可通行道路一路挖掘，求能挖到的最大地雷數，並輸出其中一條最佳挖掘路線。

Constraints

約束條件

$1 \le n \le 20$
第 $i$ 個地窖有非負整數個地雷
道路只可能由編號較小的地窖通往編號較大的地窖，因此不存在環
若存在多條最佳路徑，輸出任意一條即可

思路：有向無環圖上的最大權路徑

這題的核心不是「從哪裡開始走」，而是：對每一個地窖，都先算出「如果從這裡開始，最多還能挖到多少地雷」。

因為道路永遠只會通往編號更大的地窖，整張圖天然是一張有向無環圖。這個性質很重要：一旦從某個地窖往後走，後面的選擇不可能再回到前面，所以每個位置的最佳結果可以由後繼位置的最佳結果推出。

關鍵觀察

從某個地窖出發時，總收益等於「目前地窖的地雷數」加上「所有可前往地窖中，後續收益最大的那一個」。如果沒有任何可前往的地窖，收益就是目前地窖本身。

因此狀態可以理解為：

從某個地窖出發，沿著合法道路能挖到的最大地雷總數。

算出每個起點的狀態值後，再從所有地窖中挑出狀態值最大的起點，就是答案路徑的開頭。

方法一：記憶化搜尋

第一種寫法從「我要知道某個起點的最佳收益」出發，用深度優先搜尋往後探索。

若目前地窖可以通往幾個後續地窖，便分別詢問那些後續地窖的最佳收益，取其中最大值，再加上目前地窖的地雷數。由於不同起點可能會走到相同的後續地窖，若每次都重新搜尋，會產生重複計算；因此用快取保存每個地窖的狀態值。

為什麼這樣不會無限遞迴？

每條道路都只會往編號更大的地窖走，搜尋深度一定有限，不可能繞回已經走過的位置。

當所有地窖的最佳收益都能透過搜尋取得後，選出收益最大的起點。接著根據狀態轉移關係還原路徑：從目前位置出發，尋找一個能讓「目前地雷數 + 後續最佳收益」等於目前最佳收益的下一個位置，持續前進直到沒有更後面的可接續位置。

正確性直覺

記憶化搜尋實際上是在枚舉目前位置的所有下一步選擇，並假設下一步之後也都採用最佳策略。因為圖中沒有環，後續問題與前面如何到達無關，所以每個位置只需要保留一個最佳狀態值。

複雜度分析

時間複雜度： $\mathcal{O}(n^2)$ ，讀入道路矩陣需要 $\mathcal{O}(n^2)$ ，每條道路在搜尋中最多被檢查一次。
空間複雜度： $\mathcal{O}(n^2)$ ，儲存圖的鄰接關係；快取與遞迴深度為 $\mathcal{O}(n)$ 。

方法二：反向動態規劃

第二種寫法直接利用「道路只往後走」這件事，從編號最大的地窖一路往前計算。

對某個地窖來說，它能前往的地窖編號都比自己大。只要從後往前處理，那些後續地窖的最佳收益一定已經算好；此時只要在所有可前往地窖中取最大值，再加上目前地窖的地雷數即可。

這和記憶化搜尋本質相同，只是計算順序不同：

兩種方法的關係

記憶化搜尋是「需要某個狀態時才遞迴計算」；反向動態規劃則是「按照保證依賴已完成的順序，主動把所有狀態算完」。

完成狀態計算後，同樣選出收益最大的起點，並依照狀態值的等式關係回推出一條最佳路徑。

常見錯誤

這題不能單純選地雷數最多的地窖，也不能每一步貪心選下一個地雷數最多的地窖。某一步看起來較少的地雷，後面可能接上一段更大的收益，因此必須比較「後續整條路徑」的總收益。

複雜度分析

時間複雜度： $\mathcal{O}(n^2)$ ，讀入道路矩陣與枚舉後繼道路皆為二次量級。
空間複雜度： $\mathcal{O}(n^2)$ ，主要用於儲存圖；狀態陣列為 $\mathcal{O}(n)$ 。

Code

方法一：記憶化搜尋

from functools import cache


def solve():
    n = int(input())
    A = list(map(int, input().split()))

    g = [[] for _ in range(n)]
    for u in range(n - 1):
        vs = list(map(int, input().split()))
        for v, s in enumerate(vs, start=u + 1):
            if s == 1:
                g[u].append(v)

    @cache
    def dfs(u: int) -> int:
        if u >= n:
            return 0
        res = 0
        for v in g[u]:
            res = max(res, dfs(v))
        return res + A[u]

    st = max(range(n), key=dfs)

    u = st
    path = []
    while u < n:
        path.append(u + 1)
        v = u + 1
        while v < n and dfs(v) + A[u] != dfs(u):
            v += 1
        u = v

    print(*path)
    print(dfs(st))


if __name__ == "__main__":
    solve()

方法二：反向動態規劃

def solve():
    n = int(input())
    A = list(map(int, input().split()))

    g = [[] for _ in range(n)]
    for u in range(n - 1):
        vs = list(map(int, input().split()))
        for v, s in enumerate(vs, start=u + 1):
            if s == 1:
                g[u].append(v)

    f = [0] * n
    for u in range(n - 1, -1, -1):
        f[u] = A[u]
        for v in g[u]:
            f[u] = max(f[u], f[v] + A[u])

    st = max(list(range(n)), key=lambda x: f[x])

    u = st
    path = []
    while u < n:
        path.append(u + 1)
        v = u + 1
        while v < n and f[v] + A[u] != f[u]:
            v += 1
        u = v

    print(*path)
    print(f[st])


if __name__ == "__main__":
    solve()