HDU 1561 树形DP+有依赖的背包

此题的依赖关系为选子节点必须选其根节点

可以转换成分组背包，子节点和根在一个分组内，具体参见 背包九讲

也可见：http://www.cnblogs.com/gentleh/archive/2013/03/19/2969890.html

代码有注释

#include<stdio.h>
#include<string.h>
#include<vector>
using namespace std;
#define  maxn 220
vector<int> vec[maxn];
int val[maxn];
int dp[maxn][maxn];//dp[i][j]以i为根节点选j个地方获得的最大值
int n,m;
void init()
{
    for(int i=0;i<maxn;i++)
    vec[i].clear();
    memset(dp,sizeof(dp));
}
void dfs(int rt)
{
    dp[rt][1]=val[rt];//选1个必然先它本身
    int sz=vec[rt].size();
    for(int i=0;i<sz;i++)
    {
        int v=vec[rt][i];
        dfs(v);//递归到根节点
        for(int j=m+1;j>=1;j--)  //分组背包，j从m+1..1而不是1..m+1是为了满足dp[i]是由dp[i-1]转换而来
        {
            for(int k=1;k<j;k++)
            dp[rt][j]=max(dp[rt][j],dp[rt][j-k]+dp[v][k]);//dp[v][k]构成了一个新节点
        }
    }
}

int main()
{
    freopen("in.txt","r",stdin);
    while(scanf("%d%d",&n,&m)==2&&(n||m))
    {
        init();
        int i,a,b;
        for(i=1;i<=n;i++)//建图，原图为森林，这里把0作为根转换成了树
        {
            scanf("%d%d",&a,&b);
            vec[a].push_back(i);
            val[i]=b;
        }
        val[0]=0;
        dfs(0);
        printf("%dn",dp[0][m+1]);//以0为根选m+1个，其中包含0
    }
    return 0;
}

（编辑：安卓应用网）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!