题目描述
blablabla
动态规划
样例
输入
6
5 10 20 5 4 5
1 2
1 4
2 4
3 4
4 5
4 6
5 6
0 0
输出
3-4-5-6
34
C++ 代码
#include <bits/stdc++.h>
using namespace std;
int main()
{
long f[201] = {0}, w[201], c[201] = {0};
bool a[201][201] = {0};
long n, x, y, l = 0, k = 0, maxx;
memset(f, 0, sizeof(f));
memset(c, 0, sizeof(c));
memset(a, 0, sizeof(a));
cin >> n;
for(int i = 1; i <= n; i++) cin >> w[i]; //w记录地雷数
do{
cin >> x >> y;
if(x && y) a[x][y] = 1; //a记录x到y联通
}while(x || y);
f[n] = w[n]; //初始边界
for(int i = n - 1; i >= 1; i--){ //倒推
for(int j = i + 1; j <= n; j++)
if(a[i][j] && f[j] > l) l = f[j], k = j;
f[i] = l + w[i]; //f记录每点最大值
c[i] = k; //c记录最优路径
}
k = 1;
for(int i = 2; i <= n; i++)
if(f[i] > f[k]) k = i; //计算总路径最大值
maxx = f[k];
cout << k; ///
k = c[k]; ///
while(k){ ///
cout << "-" << k; ///
k = c[k]; ///顺序输出
}
cout << endl;
cout << maxx << endl;
return 0;
}