没看出来动规怎么做，看到n <= 20,直接一波暴搜，过了。
#include<cstdio>
#include<cstring>
#include<algorithm>
#define REP(i, a, b) for(int i = (a); i < (b); i++)
using namespace std;const int MAXN = 25;
int g[MAXN][MAXN], a[MAXN], f[MAXN];
int vis[MAXN], path[MAXN], n;int dfs(int cur)
{vis[cur] = 1;int t = 0;REP(i, 0, n) if(!vis[i] && g[cur][i]){int temp = dfs(i);if(t < temp){t = temp;path[cur] = i;}}vis[cur] = 0;return a[cur] + t;
}int main()
{scanf("%d", &n);REP(i, 0, n) scanf("%d", &a[i]);REP(i, 0, n)REP(j, i + 1, n)scanf("%d", &g[i][j]);int ans = 0, st;REP(i, 0, n){memset(path, -1, sizeof(path));memset(vis, 0, sizeof(vis));int t = dfs(i);if(ans < t){st = i;ans = t;memcpy(f, path, sizeof(f));}}for(int p = st; p != -1; p = f[p]) printf("%d ", p + 1);puts("");printf("%d\n", ans);return 0;
}然后我还是想想动规怎么做吧
因为只能往下挖，所以最后一个地窖是挖不了的
所以我们倒着推
我们设f[i]为从i开始能挖到的最大地雷
那么有
f[i] = f[j] + a[i]; i < j, i与j连接
#include<cstdio>
#include<cstring>
#include<algorithm>
#define REP(i, a, b) for(int i = (a); i < (b); i++)
using namespace std;const int MAXN = 25;
int g[MAXN][MAXN], a[MAXN], f[MAXN];
int path[MAXN], n;int main()
{memset(path, -1, sizeof(path));scanf("%d", &n);REP(i, 0, n) scanf("%d", &a[i]);REP(i, 0, n)REP(j, i + 1, n)scanf("%d", &g[i][j]);int ans = 0, st;for(int i = n - 1; i >= 0; i--){f[i] = a[i];REP(j, i + 1, n)if(g[i][j] && f[i] < f[j] + a[i]){f[i] = f[j] + a[i];path[i] = j;}if(ans < f[i]){ans = f[i];st = i;}}for(int p = st; p != -1; p = path[p]) printf("%d ", p + 1);puts("");printf("%d\n", ans);return 0;
}