注意，题目里的边都是有向边，只能从前往后。

因为只能是单向边，所以只需要计算以每个点为终点能挖的最大地雷数，这就是dp的状态。

更新dp[i]的时候只需要考虑所有能到达i的前一个节点dp[j]+当前地雷mine[i]的最大值即可。

$dp[i] = max(dp[j]) + mine[i]$

#include <cstdio>
#include <vector>
using namespace std;

void printPath(vector<int>& from, int x) {
    if (!x) return;
    printPath(from, from[x]);
    printf("%d ", x);
}

int main(int argc, char* argv[]) {
    int n;
    scanf("%d", &n);
    vector<int> mine(n+1);
    vector<int> f(n+1);
    for (int i = 1; i <= n; ++i) scanf("%d", &mine[i]), f[i] = mine[i];
    vector<vector<bool>> has(n+1, vector<bool>(n+1, false));
    int flag;
    for (int i = 1; i < n; ++i) {
        for (int j = i + 1; j <= n; ++j) {
            scanf("%d", &flag);
            has[i][j] = flag == 1;
        }
    }
    int ans = 1;
    vector<int> from(n+1, 0);
    for (int i = 1; i < n; ++i) {
        for (int j = i + 1; j <= n; ++j) {
            if (!has[i][j]) continue;
            int tmp = f[i] + mine[j];
            if (tmp > f[j]) {
                f[j] = tmp;
                from[j] = i;
            }
        }
        if (f[i+1] > f[ans]) ans = i+1;
    }
    printPath(from, ans);
    printf("\n%d\n", f[ans]);
    return 0;
}

original refer