信息学奥赛一本通TT1262-挖地雷

解题思路:DP 逆推， 邻接矩阵

注意事项:

参考代码:

#include<iostream>
#include<algorithm>
using namespace std;
const int N = 2e2 + 10;
int g[N][N],f[N],a[N],path[N];
int main()
{
	int x, y, n;
	cin >> n;
	for(int i = 1; i <= n; i ++ ) {
		cin >> a[i];
		g[i][i] = 1;
	}
	
	cin >> x >> y;
	while(!(x == 0 && y == 0)){
		g[x][y] = 1;
		cin >> x >> y;
	}
	//f[i] 以i节点为结尾的最多地雷数
	for(int i = n; i >= 1; i --){
		for(int j = i; j <= n; j ++)
			if(g[i][j])
				if(f[i] < f[j] + a[i]){
					f[i] = f[j] + a[i];
					path[i] = j;
				}
	}
	int mx = f[1] , k = 1;
	for(int i = 1; i <= n; i ++)
		if (mx < f[i]) {
			k = i;
			mx = f[i];
		}
	cout << k;
	while (path[k] && k != path[k]) {
		k = path[k];
		cout << '-' << k;		
	}
	cout << endl << mx;
	return 0;
}