题目描述

在一个地图上有 N (N≤20) 个地窖，每个地窖中埋有一定数量的地雷。同时，给出地窖之间的连接路径。当地窖及其连接的数据给出之后，某人可以从任一处开始挖地雷，然后每次可以移动到一个编号比当前节点大且联通的节点去挖地雷，当无满足条件的节点时挖地雷工作结束。设计一个挖地雷的方案，使某人能挖到最多的地雷。

输入格式

有若干行。

第 1 行只有一个数字，表示地窖的个数 N。

第 2 行有 N 个数，分别表示每个地窖中的地雷个数。

第 3 行至第 N+1 行表示地窖之间的连接情况：

第 3 行有 n−1 个数（0 或 1），表示第一个地窖至第 2 个、第 3 个 … 第 n 个地窖有否路径连接。如第 3 行为 11000⋯0，则表示第 1 个地窖至第 2 个地窖有路径，至第 3 个地窖有路径，至第 4 个地窖、第 5 个 … 第 n 个地窖没有路径。

第 4 行有 n−2 个数，表示第二个地窖至第 3 个、第 4 个 … 第 n 个地窖有否路径连接。

……

第 n+1 行有 1 个数，表示第 n−1 个地窖至第 n 个地窖有否路径连接。（为 0 表示没有路径，为 1 表示有路径）。

输出格式

第一行表示挖得最多地雷时的挖地雷的顺序，各地窖序号间以一个空格分隔，不得有多余的空格。

第二行只有一个数，表示能挖到的最多地雷数。

输入输出样例

输入 #1复制

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

输出 #1复制

1 3 4 5
27

说明/提示

【样例解释】 

 最优路径为 1→3→4→5，结果为 27。

【题目来源】

NOIP 1996 提高组第三题。

思路：

求一条路径上的最大地雷数，首先想到的就是DFS，题目的数据量也不大

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

int n,m;
vector<int> nums;
int edge[21][21];
int vis[21]={0};
int res=-1;
vector<int> pathRes;

typedef struct Group{
	int x,y;
	bool operator<(Group g) const{
		if(x!=g.x) return x<g.x;
		else return y<g.y;
	}	
}G;
const ll mod = 1e9+7;

void dfs(int now,int sum,vector<int>& pathOne){
	
	int flag=0;
	for(int i=now+1; i<=n; i++){
		if(edge[now][i]&&!vis[i]){
			flag=1;
			break;	
		}
	}
	if(flag==0){
		if(sum>res){
			res = sum;
			vector<int>().swap(pathRes);
			for(auto x : pathOne){
				pathRes.push_back(x);
//				cout<<x<<" ";	
			}
//			cout<<endl;
//			pathRes = pathOne;
		}
		return;
	}
	
	for(int i=now+1; i<=n; i++){
			
		if(edge[now][i]&&!vis[i]){
			vis[i]=1;
			pathOne.push_back(i);
			dfs(i,sum+nums[i-1],pathOne);
			pathOne.pop_back();
			vis[i]=0;	
		}
	}
}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	
	cin>>n;
	for(int i=0; i<n; i++){
		int t;
		cin>>t;
		nums.push_back(t);
	}
	
	for(int i=1; i<n; i++){
		for(int j=i+1; j<=n; j++){
			cin>>edge[i][j];
		}
	}

	for(int i=1; i<=n; i++){
//		cout<<i<<endl;
		vector<int> pathOne;
		pathOne.push_back(i);
		vis[i]=1;
		dfs(i,nums[i-1],pathOne);
		vis[i]=0;
//		for(auto x: pathRes) cout<<x<<" ";
//		cout<<endl;
	}
	
	for(int i=0; i<pathRes.size(); i++){
		if(i==0) cout<<pathRes[i];
		else cout<<" "<<pathRes[i];
	}
	cout<<endl;
	cout<<res<<endl;
	
	return 0;
}

思路提升：

题目要求在有向无环图（因为节点编号严格递增）中寻找一条路径，使得路径上节点的地雷总数最大。由于节点百年好严格递增，图本质上是无环的，这为动态规划提供基础。

我们定义dp[i]为从i节点出发可以得到的最大地雷数，那么我们可以知道，dp[i] = max(nums[i],nums[i]+dp[j])，其中j大于i。所以，为了在推dp[i]时具有dp[j]这个信息，我们需要从后往前推。

由于我们需要输出最后的路径，所以我们还得使用一个数组来记录每个节点正确的后继节点。

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

int n,m;

typedef struct Group{
	int x,y;
	bool operator<(Group g) const{
		if(x!=g.x) return x<g.x;
		else return y<g.y;
	}	
}G;
const ll mod = 1e9+7;

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	
	cin>>n;
	vector<int> nums(n);
	for(int i=0; i<n; i++) cin>>nums[i];
	
	vector<vector<int>> edge(n+1,vector<int>(n+1,0));
	for(int i=1; i<n; i++){
		for(int j=i+1; j<=n; j++){
			cin>>edge[i][j];
		}
	}
	
	vector<int> next(n+1,-1);
	
	vector<int> dp(n+1);
	for(int i=n; i>=1; i--){
		dp[i] = nums[i-1];
		for(int j=i+1; j<=n; j++){
			if(edge[i][j]&&nums[i-1]+dp[j]>dp[i]){
				dp[i] = nums[i-1]+dp[j];
				next[i] = j;
			}
		}
	}
	
	int maxn = dp[1];
	int start = 1;
	for(int i=2; i<=n; i++){
		if(dp[i]>maxn){
			maxn = dp[i];
			start = i;
		}
	}
	
	vector<int> res;
	for(int i=start; i!=-1; i=next[i]){
		res.push_back(i);
	}
	for(int i=0; i<res.size(); i++){
		if(i==0) cout<<res[i];
		else cout<<" "<<res[i];
	}
	cout<<endl;
	cout<<maxn<<endl;
	return 0;
}