1.DFS

#include<bits/stdc++.h>
using namespace std;

const int N = 25;
int h[N], e[N], ne[N], idx = 1;
int w[N], n, st[N];
int path[N], res, cnt;
int ans[N];

// f[i]表示以i为终点的所有路径的最大地雷数
// 以倒数二个结点划分为k个集合,f[i] = max(f[i] + f[k]) 

void add(int a, int b){
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}

void dfs(int u, int t)
{
    int flag = 0;
    for(int i = h[u]; i; i = ne[i])
        if(!st[e[i]]) flag = 1;
    if(flag == 0){
        int sum = 0;
        for(int i = 0; i < t; i ++) sum += w[path[i]];
        if(sum > res){
            for(int i = 0; i < t; i ++) ans[i] = path[i];
            res = sum; cnt = t;
        }
    }

    for(int i = h[u]; i; i = ne[i])
    {
        int j = e[i];
        if(!st[j]){
            st[j] = 1;
            path[t] = j;
            dfs(j, t + 1);
            st[j] = 0;
        }
    }
}

int main()
{
    cin >> n;

    for(int i = 1; i <= n; i ++) cin >> w[i];

    for(int i = 1; i <= n - 1; i ++){
        for(int j = i + 1; j <= n; j ++){
            int b; 
            cin >> b;
            if(b) add(i, j);
        }
    }


    for(int i = 1; i <= n; i ++ ){
        st[i] = 1;
        path[0] = i;
        dfs(i, 1);
        st[i] = 0;
    }

    for(int i = 0; i < cnt; i ++ ) cout << ans[i] << " ";
    cout << endl << res;

}

2.DP

#include<bits/stdc++.h>
using namespace std;

const int N = 25;
int g[N][N];
int w[N], n;
int path[N];
int f[N];

// f[i]表示以i为终点的所有路径的最大地雷数
// 以倒数二个结点划分为k个集合

int main()
{
    cin >> n;

    for(int i = 1; i <= n; i ++) cin >> w[i];

    for(int i = 1; i <= n - 1; i ++){
        for(int j = i + 1; j <= n; j ++){
            int b; 
            cin >> b;
            if(b) g[i][j] = 1;
        }
    }

    f[1] = w[1];
    for(int i = 2; i <= n; i ++){
        for(int j = 1; j <= n; j ++){
            if(g[j][i] && f[j] + w[i] > f[i]){
                f[i] = f[j] + w[i];
                path[i] = j;
            }
        }
    }

    int t = 0, ans = 0;
    for(int i = 1; i <= n; i ++){
        if(f[i] > ans){
            t = i;
            ans = f[i];
        }
    }

    stack<int> stk;
    for(int i = t; i; i = path[i]) stk.push(i);
    while(stk.size()){
        cout << stk.top() << " ";
        stk.pop();
    }
    cout << endl;
    cout << ans;

}