P2196 挖地雷

另外本题还要注意一下他要输出路径，所以开一个数组记录一下后继结点

#include<iostream>
#include<cstdio>

using namespace std;

const int N = 30, INF = 0x3f3f3f3f;

int f[N];
int w[N];
int g[N][N];
int n;
int p[N];

int main(){
    cin >> n;
    
    for(int i = 1; i <= n; i ++) cin >> w[i];
    
    for(int i = 1; i <= n; i ++)
        for(int j = i + 1; j <= n; j ++)
            cin >> g[i][j];
    
    f[n] = w[n];
    
    for(int i = n - 1; i >= 1; i --){
        int k = 0, maxv = -INF;
        for(int j = i + 1; j <= n; j ++)
            if(g[i][j])
                if(maxv < f[j] + w[i]) maxv = f[j] + w[i], k = j;
        if(k) p[i] = k, f[i] = maxv;
        else f[i] = w[i];
    }
    
    int k = 0, maxv = -INF;
    for(int i = 1; i <= n; i ++)
        if(maxv < f[i]) maxv = f[i], k = i;
    
    cout << k;
    while(p[k]){
        k = p[k];
        cout << ' ' << k;
    }
    
    puts("");
    cout << maxv << endl;
    
    return 0;
}