hdu 1561 依赖背包

题意：n座城堡，每个里面都有宝物，要求在你可以攻占m个城堡得到的最多的宝物，但是如果要攻破一个城堡，必须要攻破它依赖的那个城堡，例如，如果a依赖b，那么如果想要攻破a就必须先攻破b。把每个城堡看作是物品，那么这个物品的城堡数量是1，价值就是宝物了。

解题思路：根据题意知道这种关系会形成一颗多叉树，根节点是0.从P=0开始，

1、遍历所有P的孩子，遇到某个孩子还有孩子，就把该节点当作P，继续1，直到遍历完所有的节点，如果P的所有孩子都没有孩子，那么转到2，存在有的孩子有孩子，转到3；

2、对P的所有孩子进行01背包，假设P的价值是Vp，P共有n个孩子，然后对每个孩子进行01背包（因为对于每个城堡只能取一次），那么可以得到城堡数量从0到n对应的最大价值（0对应的肯定是0了），用dp[i]表示，i代表城堡数量，dp[i]代表价值，接着从i=0开始，都加上P的价值Vp（因为所有的物品都依赖P），同时城堡的个数也加1；最后把得到的n+1个物品保存到P点，这样，这些物品就相当于分组背包里面的一组背包了，储存在castle里面，然后接着步骤1的遍历；

3、这个就很简单了，由于已经遍历过P所有孩子了，所以，只需要再从头开始遍历一遍所有孩子，如果遍历的孩子还有孩子，那么就把它的所有孩子当作是分组背包处理，如果遍历的孩子没有孩子，那么就当01背包处理，最后会得到一个城堡数量从0到m（也就是题目给的城堡数量的上限，以为不确定P的所有孩子的个数，所以就用最大的m）对应的最大价值，这个时候，如果P是0，那么就输出dp[m]就好了，如果不是，像2一样，dp[i]代表的价值都加上P的价值，数量也加1，也储存在castle里面，继续步骤1的遍历；

具体代码如下：

（提示：结构体s[i]代表城堡i的信息：num表示城堡的数量，value代表价值，key是自身的序号，depend代表i依赖的城堡编号；list castle[i]记录依赖i的城堡的信息）

#include <cstdio>
#include <string.h>
#include <iostream>
#include <list>

using namespace std;
#define N 205
struct ss{
    int num,value,key,depend;//物品的个数，价值，自身的序号，依赖的序号；
}s[N],one;
list <ss> castle[N];
int dp[N],m;
void fun(int n)
{
	int num=0,i,j,k,minn;
	list <ss>::iterator p,q;
	p=castle[n].begin();
	while(p!=castle[n].end())
	{
		if(castle[(*p).key].size()!=0)
			fun((*p).key);
		p++;
	}	
	memset(dp,sizeof(dp));
	p=castle[n].begin();
	while(p!=castle[n].end())
	{
		if(castle[(*p).key].size()!=0)
		{			
			for(i=m;i>=0;i--)
			{
				q=castle[(*p).key].begin();
				while(q!=castle[(*p).key].end())
				{
					if(i-(*q).num>=0)
					dp[i]=max(dp[i],dp[i-(*q).num]+(*q).value);
					q++;
				}
			}
		}
		else
		{
			for(i=m;i>=(*p).num;i--)
				dp[i]=max(dp[i],dp[i-(*p).num]+(*p).value);
		}
		p++;
	}
	
	castle[n].clear();
	if(!n)
		cout<<dp[m]<<endl;
	else
	{
		one.depend=n;one.key=n;
		for(i=m;;i--)
		{
			if(dp[i])
			{
				one.num=i+1;one.value=dp[i]+s[n].value;
				castle[n].push_back(one);
			}
			else
			{
				one.num=1;one.value=s[n].value;
				castle[n].push_back(one);
				break;
			}
		}
	}
	
}

int main()
{
    int n;
    while(cin>>n>>m)
    {
		if(!n&&!m)
			return 0;
        int i,x;
        for(i=0;i<=n;i++)
			castle[i].clear();
		for(i=0;i<n;i++)
		{
			scanf("%d%d",&s[i+1].depend,&s[i+1].value);
			s[i+1].num=1;	s[i+1].key=i+1;
			castle[s[i+1].depend].push_back(s[i+1]);
		}
		fun(0);	
    }
}