hdu 1561 （树形dp+依赖背包）

矫情吗；* 2022-08-21 03:23 183阅读 0赞

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

分析：

和依赖背包有些类似，就是想要取一个值的时候要先取一个其他的值。  这个题目明显可以先根据依赖关系建一棵树，然后就是考虑怎么对这棵树进行dp了，所以是树形dp。

这种题目也是第一次见到，可能有一个套路吧。dp\[i\]\[j\] 就是在以i为根的子树里面取j个节点的最大值。最终结果就是dp\[0\]\[m\]，这棵树的根节点为0.

//方程dp[n][j]=max(dp[n][j],dp[n][j-k]+dp[son[n][i]][k])
    //表示在第i个n的子点中选k个点加上目前k号点选j-k个点与直接在k号点选j个点谁更优

#include <cstdio>
    #include <cstring>
    #include <cmath>
    #include <algorithm>
    #include <algorithm>
    #include <queue>
    #include <stack>
    #include <map>
    
    using namespace std ;
    #define mem(a) memset(a,0,sizeof(a))
    #define inf 100000005
    
    int const maxn = 205;
    int dp[maxn][maxn];
    vector<int>son[maxn];
    
    void dfs(int n,int left)
    {
        int len = son[n].size();
        for(int i = 0 ; i < len ; i++)    //节点n的所有儿子节点
        {
            if(left>1)dfs(son[n][i],left-1);
            for(int j = left ; j >= 1 ; j--)
            {       //一个类背包的求解
                for(int k = 1 ; k <= j ; k++)
                {
                    dp[n][j+1] = max(dp[n][j+1] , dp[n][j+1-k]+dp[son[n][i]][k]);
                    //方程dp[n][j]=max(dp[n][j],dp[n][j-k]+dp[son[n][i]][k])
                    //表示在第i个n的子点中选k个点加上目前k号点选j-k个点与直接在k号点选j个点谁更优
                }
            }
        }
    }
    
    int main()
    {
        int n,m;
        while(scanf("%d%d",&n,&m)&&(m+n))
        {
            mem(dp);
            for(int i = 0 ; i <= n ; i++)
            {
                son[i].clear();
            }
            for(int i = 1 ; i <= n ; i++)
            {
                int a,b;
                scanf("%d%d",&a,&b);
                dp[i][1] = b ;   //初始化，一个节点处要是只取一个节点的话，肯定是本身
                son[a].push_back(i) ;  //要想i必须先a，所以i是a的儿子
            }
            m++;     //增加了一个节点0
            dfs(0,m);
            printf("%d\n",dp[0][m]);
        }
        return 0 ;
    }