首页 > 其他 > 详细

HDU 1011 Starship Troopers 树DP

时间:2014-06-24 18:24:45      阅读:356      评论:0      收藏:0      [点我收藏+]

本题也是挺特别的题目,因为要递归到树的叶子节点然后初始化。

一开始看题也很困难,以为只是一条路径的最大获利计算,使用保存路径,然后DP,结果WA了。

原来本题是需要分路径探索的,就是说每一个分岔路都可以分兵探索下去,如果兵力不足就结束,看最大收益是多少。

题目并没有说的那么清楚,也许看题目也考人的IQ吧,要放聪明点。

本题是考人的递归能力,动态规划法能力,总结起来难度还是很高的。


#include <stdio.h>
#include <vector>
#include <algorithm>
#include <math.h>
using namespace std;

int N, M, a, b;
vector<vector<int> > *ca;
vector<bool> *vis;
vector<vector<int> > *tbl;
vector<vector<int> > *tu;
//不使用全局变量,就要传递6个变量给treeDP
void treeDP(int r)
{
	(*vis)[r] = true;
	int soldiers = ((*ca)[r][0]+19)/20;

	//单独是本节点的时候,多少soldiers以上能拿到brain,递归到底就作为初始化条件了
	for (int i = soldiers; i <= M; i++) (*tbl)[r][i] = (*ca)[r][1];

	for (int i = 0; i < (int)(*tu)[r].size(); i++)
	{
		int u = (*tu)[r][i];
		if ((*vis)[u]) continue;
		treeDP(u);//深度递归到底出来,就已经初始化好最小情况了

		for (int j = M-1; j >= soldiers; j--)
		{//j为本节点兵力
			for (int k = 1; k <= M-j; k++)
			{//k为分配多少给孩子节点的兵力
				(*tbl)[r][j+k]=max((*tbl)[r][j+k],(*tbl)[r][j]+(*tbl)[u][k]);
			}//试探性分配兵力,从1分配到M-soldiers给孩子节点
		}
	}
}

int main()
{
	while (scanf("%d %d", &N, &M) && -1 != N)
	{
		vector<vector<int> > caverns(N+1, vector<int>(2));
		for (int i = 1; i <= N; i++)
		{
			scanf("%d %d", &caverns[i][0], &caverns[i][1]);
		}
		ca = &caverns;//减少传递参数

		vector<vector<int> > tunnels(N+1);
		for (int i = 1; i < N; i++)
		{
			scanf("%d %d", &a, &b);
			tunnels[a].push_back(b);
			tunnels[b].push_back(a);
		}
		tu = &tunnels;

		if(M == 0) puts("0");
		else
		{
			vector<bool> visited(N+1, false);
			vis = &visited;

			vector<vector<int> > table(N+1, vector<int>(M+1));
			tbl = &table;

			treeDP(1);
			printf("%d\n", table[1][M]);
		}
	}
	return 0;
}



HDU 1011 Starship Troopers 树DP,布布扣,bubuko.com

HDU 1011 Starship Troopers 树DP

原文:http://blog.csdn.net/kenden23/article/details/33749869

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!