hdu 1561 The more, The Better (树形dp)

题意：每个城堡有一定价值的财宝，可以选择攻打m个城市。但是攻打有些城市之前一定要先

攻打其他的城市。现在已知每个城堡中财宝的价值和城市间的依赖关系。求选择攻打m个城市

能获得的最大价值。

分析：

虽然题目没有明确指出。但是很明显这是一个存在依赖关系的背包问题，而且是依赖中有依赖（可能攻打

a必须先攻打b，而攻打b又要先攻打c）

我们把这种依赖关系用树表示，必须先攻打的是父亲，后攻打的是他的儿子。

dp[i][j]表示选择以i节点为根的子树中j个节点得到的最大财富值。

这样就有两种方案，分别对应了两个子问题：

1】选择以i的第x个儿子t为根的子树中的j-k个节点，然后选择以i为根的除x为根的子树外的其他子节点

（包括它自己）的k个节点。（注意这里出现了子树中的子树的概念，就是有j-k个节点是集中在子树的

子树中选）

2】直接在以i为根的树中（只涉及到i的下一层，也就是i的儿子）选j个节点。

我们已经知道dp[i][1]=val（输入的财宝价值），因为选1个一定会选自己。

依赖关系形成森林，进行树形dp前要把森林转化为树，所以

要加一个根节点：0。结果就是dp[0][m+1] （包括增加的根节点一共m+1个点）

#include<cstdio>
#include<iostream>
#include<cstring>
using namespace std;

int mp[210][210],num[210],dp[210][210];
int vis[210],n,m;

int maxx(int x,int y)
{
    return x>y?x:y;
}

void dfs(int r)
{
    vis[r]=1;
    for(int i=1;i<=num[r];i++)
    {
        int t=mp[r][i];
        if(!vis[t])
            dfs(t);
        for(int j=m;j>=2;j--)
        {
            for(int k=1;k<j;k++)
            {
                if(dp[t][j-k]!=-1 && dp[r][k]!=-1)
                    dp[r][j]=maxx(dp[r][j],dp[t][j-k]+dp[r][k]);
            }
        }
    }
}

int main()
{
    int a,b;
    while(scanf("%d%d",&n,&m)!=EOF)
    {
        if(n==0 && m==0)
            break;
        memset(num,0,sizeof(num));
        dp[0][1]=0;
        for(int i=1;i<=n;i++)
        {
            scanf("%d%d",&a,&b);
            dp[i][1]=b;
            mp[a][++num[a]]=i;
        }
        m++;
        for(int i=0;i<=n;i++)
        {
            vis[i]=0;
            dp[i][0]=0;
            for(int j=2;j<=m;j++)
                dp[i][j]=-1;
        }
        dfs(0);
        printf("%d\n",dp[0][m]);
    }
    return 0;
}

hdu 1561 The more, The Better (树形dp)

原文：http://blog.csdn.net/u012841845/article/details/18716181