挖地雷

题目描述

在一个地图上有N个地窖，依次编号为1…N，每个地窖中埋有一定数量的地雷。同时，给出地窖之间的连接路径。 例如在下图中： 上图表示，地窖1可以挖到地窖2，地窖3；地窖2可以挖到地窖4；地窖3可以挖到地窖4，地窖5；地窖4可以挖到地窖5。 当地窖及其连接的数据给出之后，某人可以从任一处开始挖地雷，然后可以沿着某条路径接着往下挖（仅能选择一条路径），当某个地窖无连接时挖地雷工作结束。 试设计一个挖地雷的方案，使某人能挖到最多的地雷。

输入格式

第1行：1个整数N（1<=N<=20），表示地窖的个数 第2行：N个用空格分开的整数，第i个整数表示地窖i里所埋的地雷个数 第3行~N+1行：第i+2行有n-i个用空格分开的整数，第i+2行描述第i个地窖与第i+1,i+2,…,n个地窖的连接情况。某个整数为1，表示有路径相连，为0， 表示无路径相连。

输出格式

第1行：1个整数，表示能挖到的最多的地雷数量 第2行：若干个用空格分开的整数，表示所挖的地窖编号。编号按所挖地窖的顺序输出，若有多个方案都得到最多的地雷数量，则输出编号尽可能小的一组。

输入样例

5 10 8 4 7 6 1 1 0 0 0 1 0 1 1 1

输出样例

31 1 2 4 5

地窖中的交错关系可以想象成为一个有向图，比如样例可以表示成这样：

我们枚举每一个地窖，然后往他的每一个邻接点转移：

设$dp[i]$表示走到当前这个地窖，不管前面是怎么走的，只要走到当前这个地窖的能挖到最多的地雷。

$dp[i]=max(dp[i],dp[j]+w[i])$

$dp[j]$表示$i$是从$j$走过来的

注意做dp的时候要记录一下哪一个地窖是从哪一个地窖来的。

#include <bits/stdc++.h> using namespace std; #define MAXN 1005 int n; int a[MAXN]; int dp[MAXN],pre[MAXN]; bool G[MAXN][MAXN]; int main() { cin >> n; for(int i = 1; i <= n; i++) cin >> a[i]; for(int i = 1; i < n; i++) for(int j = i + 1; j <= n; j++) cin >> G[i][j]; dp[n] = a[n]; for(int i = n - 1; i >= 1; i--) { int dpj = 0, path = 0; for(int j = i + 1; j <= n; j++) { if(G[i][j] == 1 && dp[j] > dpj) { dpj = dp[j]; path = j; } } dp[i] = dpj + a[i]; pre[i] = path; } int maxx = 0, k = 1; for(int i = 2; i <= n; i++) if(dp[i] > dp[k]) k = i; cout << dp[k] << endl; while(k) { cout << k << " "; k = pre[k]; } return 0; }