解题思路

n 个地窖，每个地窖有一定数量的地雷。地窖之间有单向通路（小序号指向大序号）。从任意地窖开始，沿通路挖下去，问最多能挖到多少地雷，并输出这条路径。

这是一个典型的动态规划题。因为路径都是从小序号指向大序号，没有回路，所以可以从后往前推。

思路：

设 dp[i] 表示从地窖 i 开始挖，最多能挖到的地雷数。

那么 dp[i] = 地窖 i 的地雷数 + 从 i 能去的下一个地窖中最多的 dp 值。

步骤：

1. 从最后一个地窖往前推（因为 i 只能去编号更大的地窖，所以先算后面的）
2. 对每个地窖 i，找所有它能去的 j（有通路 f[i][j]），选 dp[j] 最大的
3. dp[i] = a[i] + 最大的 dp[j]，并记录 i 下一步去哪（用 r[i] 记）
4. 找 dp 值最大的地窖作为起点
5. 顺着 r 数组打印整条路径，最后输出最大地雷数

为什么从后往前推？ 因为 i 只能去编号更大的地窖，所以 dp[i] 依赖 dp[i+1..n]，从后往前算就能保证用到的 dp[j] 都已经算好了。

举例：6 个地窖，地雷数 5 10 20 5 4 5，通路有 1→2、1→4、2→4、3→4、4→5、4→6、5→6。

从后往前推，最优路径是 3→4→5→6，地雷数 = 20+5+4+5 = 34。

参考代码

#include <iostream>
using namespace std;

int n, a[1005];
int dp[1005], r[1005];
bool f[210][210];

int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];

    int x, y;
    while (1) {
        cin >> x >> y;
        if (x == 0 && y == 0) break;
        f[x][y] = 1;
    }

    int idx = 0, cnt = 0;
    dp[n] = a[n];
    for (int i = n - 1; i >= 1; i--) {
        cnt = 0;
        for (int j = i + 1; j <= n; j++) {
            if (f[i][j] && dp[j] > cnt) {
                idx = j;
                cnt = dp[j];
            }
        }
        dp[i] = cnt + a[i];
        r[i] = idx;
    }

    idx = 1;
    for (int i = 2; i <= n; i++) {
        if (dp[i] > dp[idx]) idx = i;
    }
    int ans = dp[idx];

    while (idx != 0) {
        cout << idx;
        idx = r[idx];
        if (idx != 0) cout << "-";
    }
    cout << endl << ans;
    return 0;
}

复杂度分析

• 时间复杂度：O(N²)，每个地窖枚举它能去的所有地窖
• 空间复杂度：O(N²)，路径关系数组