首页 > ACM题库 > HDU-杭电 > HDU 1561 The more, The Better-动态规划-[解题报告] C++
2013
12-12

HDU 1561 The more, The Better-动态规划-[解题报告] C++

The more, The Better

问题描述 :

ACboy很喜欢玩一种战略游戏,在一个地图上,有N座城堡,每座城堡都有一定的宝物,在每次游戏中ACboy允许攻克M个城堡并获得里面的宝物。但由于地理位置原因,有些城堡不能直接攻克,要攻克这些城堡必须先攻克其他某一个特定的城堡。你能帮ACboy算出要获得尽量多的宝物应该攻克哪M个城堡吗?

输入:

每个测试实例首先包括2个整数,N,M.(1 <= M <= N <= 200);在接下来的N行里,每行包括2个整数,a,b. 在第 i 行,a 代表要攻克第 i 个城堡必须先攻克第 a 个城堡,如果 a = 0 则代表可以直接攻克第 i 个城堡。b 代表第 i 个城堡的宝物数量, b >= 0。当N = 0, M = 0输入结束。

输出:

对于每个测试实例,输出一个整数,代表ACboy攻克M个城堡所获得的最多宝物的数量。

样例输入:

3 2
0 1
0 2
0 3
7 4
2 2
0 1
0 4
2 1
7 1
7 6
2 2
0 0

样例输出:

5
13

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=1561

题目大意:给定n个地点,每个地点藏有cost[i]的宝物,取得某些宝物有时需要先取其他宝物,现在让我们选m个地点问最多可以选多少宝物?

解题思路:和Poj1155、1947一样,都是在树形结构上进行分组背包处理。本题的依赖关系可以理解成树边,到达子节点必须先经过父节点,本质是一样的,这样可以建立起一个森林,如果为每棵树的添加一个公共父节点0那就成了一棵树了,这是个实用性很强的小技巧。建立起一棵树就开始如何进行dp,如何从子节点获取信息。

    一个子节点就可以返回m个状态,每个状态表示容量为j(j<=m)时选最多的宝物,而一个子节点中只可以选择一个状态进行转移,每个节点有若干个子节点,问题就转换为分组背包,几个子节点就是几个分组背包,体积是选几个地点,价值是宝物价值。

     状态转移方程: dp[v][1] = Money[v]; (v为叶子节点)
                          dp[v][j] = max(dp[v][j],dp[v][j-i] + dp[k][i] );(v为非叶子节点,j表示用户个数,i为容量,k为v的子节点,)
    算法复杂度O(sum(num[i],num[s])) (num[i]为某个节点的叶子子孙个数,num[s]为i的子节点的叶子子孙个数)

    本题加了个剪枝,每次转移时不必都从最大容量m开始,而可以把当前可能转移的最大容量算出来进行转移,最大容量就是子节点个数,速度快了10几倍。

测试数据:

3 2
0 1
0 2
0 3

7 4
2 2
0 1
0 4
2 1
7 1
7 6
2 2


代码:

#include <stdio.h>
#include <string.h>
#define MAX 210
#define max(a,b) (a)>(b)?(a):(b)


struct node {

	int v;
	node *next;
}*head[MAX],tree[MAX];
int n,m,money[MAX];	//root表示输入时是否与根相连
int ptr,dp[MAX][MAX];


void Initial() {
	
	ptr = 1;
	memset(dp,0,sizeof(dp));
	memset(head,NULL,sizeof(head));
}
void AddEdge(int fa,int son) {

	tree[ptr].v = son;
	tree[ptr].next = head[fa];
	head[fa] = &tree[ptr++];
}
int Tree_DP(int v) {

	int i,j,k,tot = 1;
	node *p = head[v];

	
	while (p != NULL) {

		tot += Tree_DP(p->v);
		int tp = tot < m ? tot : m;		//加个剪枝,这个到目前为止能到达最大容量
		for (j = tp; j >= 1; --j)   //分组背包
			for (i = 1; i <= j; ++i)
				dp[v][j] = max(dp[v][j],dp[p->v][i]+dp[v][j-i]);
		p = p->next;
	}


	if (v != 0) {

		for (j = m; j >= 1; --j)
			dp[v][j] = dp[v][j-1] + money[v];	//必选当前节点自己
	}
	return tot;
}


int main()
{
	int i,j,k,a,b;


	while (scanf("%d%d",&n,&m),n+m) {

		Initial();
		for (i = 1; i <= n; ++i) {

			scanf("%d%d",&a,&b);
			money[i] = b;
			AddEdge(a,i);
		}


		Tree_DP(0);
		printf("%d\n",dp[0][m]);
	}
}

本文ZeroClock原创,但可以转载,因为我们是兄弟。

解题报告转自:http://blog.csdn.net/woshi250hua/article/details/7637847


  1. 第一句可以忽略不计了吧。从第二句开始分析,说明这个花色下的所有牌都会在其它里面出现,那么还剩下♠️和♦️。第三句,可以排除2和7,因为在两种花色里有。现在是第四句,因为♠️还剩下多个,只有是♦️B才能知道答案。

  2. 这道题这里的解法最坏情况似乎应该是指数的。回溯的时候
    O(n) = O(n-1) + O(n-2) + ….
    O(n-1) = O(n-2) + O(n-3)+ …
    O(n) – O(n-1) = O(n-1)
    O(n) = 2O(n-1)

  3. 站长,你好!
    你创办的的网站非常好,为我们学习算法练习编程提供了一个很好的平台,我想给你提个小建议,就是要能把每道题目的难度标出来就好了,这样我们学习起来会有一个循序渐进的过程!

  4. 站长,你好!
    你创办的的网站非常好,为我们学习算法练习编程提供了一个很好的平台,我想给你提个小建议,就是要能把每道题目的难度标出来就好了,这样我们学习起来会有一个循序渐进的过程!