首页 > 代码库 > hdu1561The more, The Better 树形dp

hdu1561The more, The Better 树形dp

2024-11-04 12:22:02   205人阅读

/*
dp[i][j]表示第i个节点及其子树取j个所得的最大值
在第i个节点的儿子节点有多个，而对于每个儿子节点及其对应的子树中选几个节点才能得到最大值
可以用背包来做
*/
#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
using namespace std;
#define maxn 210
int dp[maxn][maxn];//dp[i][j]表示第i个节点及其子树取j个所得的最大值
int value[maxn];
int vis[maxn];
vector<int> vec[maxn];
int N,M;
int dfs(int root,int remain)//remain表示到了这个节点最多能选多少节点
{
    int i;int j,k;
    int amount=0;//表示以该节点为根节点的子树的所有的节点的个数
    for(i=0;i<vec[root].size();i++)
    {
       int next=vec[root][i];
       int sum;
       sum=dfs(next,remain-1);//表示这个这个子树的节点总数
       amount+=sum;
       for(j=min(remain-1,amount);j>=1;j--)
           for(k=1;k<=sum&&k<=j;k++)
               dp[root][j]=max((dp[root][j-k]+dp[next][k]),dp[root][j]);


    }
    for(j=min(amount,remain-1);j>=0;j--)//只能选了这个节点后才能选后面的节点
    dp[root][j+1]=dp[root][j]+value[root];//所以该节点一定要加上
    return amount+1;
}
int main()
{
    /*freopen("in.txt","r",stdin);
        freopen("out.txt","w",stdout);*/
    while(scanf("%d%d",&N,&M),N||M)
    {
        int a,b;int i;
        memset(value,0,sizeof(value));
        memset(dp,0,sizeof(dp));
        for(i=0;i<=N;i++)
        vec[i].clear();
        for(i=1;i<=N;i++)
        {
            scanf("%d%d",&a,&b);
            vec[a].push_back(i);
            value[i]=b;
        }
        dfs(0,M+1);
        printf("%d\n",dp[0][M+1]);
    }
    return 0;
}















































hdu1561The more, The Better 树形dp


联系
我们