hdoj1561The more, The Better（树形dp，依赖背包）

客官°小女子只卖身不卖艺 2022-09-20 15:25 175阅读 0赞

题目：[hdoj1561The more, The Better][hdoj1561The more_ The Better]

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

分析：

分类：树形dp入门，依赖背包

做这题前又看了一遍背包9讲，感觉太经典了，尤其是泛化背包，简直是精华。这题的关系就是裸地依赖背包，用树形dp解。

首先，限制条件是选择m个物品，而每个物品最多选一次，跟0-1背包的区别在于有依赖关系，那么这层依赖关系我们可以借助于一个树来解决。借助dfs，从根节点开始dfs，然后直到叶子节点，回朔的时候进行0-1背包dp。

定义状态：dp \[ i \] \[ j \] 表示在节点i，从以i为根节点的子树下选择j个城市的最大价值

初始化：dp \[ i \] \[ j \] =val \[ i \]（i节点的价值）（1 < = j < = m）

转移方程 dp【father】【j】 = max （dp【father】【j】，dp【father】【k】+dp【child】【j-k】）；由前面的dfs可见，我们是用子节点更新父节点，用j枚举父节点选择的城市数，k枚举留给其他子节点选择城市数，那么就可以转移了

注意：此题出给很多初始节点，也就是有很多森林，我们要设置一个超级root连接子树的根节点即可。

代码：

#include <iostream>
    #include <vector>
    #include <cstring>
    #include <cstdio>
    #include <string>
    #include <algorithm>
    #include <vector>
    #define Del(a,b) memset(a,b,sizeof(a))
    const int N = 150;
    using namespace std;
    int n,m;
    int dp[N][N],vis[N];  //dp[i][j]表示在节点i，从以i为根节点的子树下选择j个城市的最大价值
    int cap[N],val[N];
    vector<int> v[N];
    
    void creat(int o)
    {
        for(int i=0; i<v[o].size(); i++)
        {
            int t=v[o][i];
            if(vis[t] == 0 && v[t].size()>0)
                creat(t);
            for(int j = m ; j > 1 ; j--)   //j>1表示此节点一定要取 0-1背包
            {
                for(int k=1; k<j; k++) //枚举给当前节点的其他子树留多少可选择的城市
                    dp[o][j]=max(dp[o][j],dp[o][k]+dp[t][j-k]);
            }
        }
    }
    
    int main(){
        while(cin >> n >> m , n&&m){
            m ++; // 加一个根节点
            Del(dp,0);
            for(int i = 1 ; i <= n ; i ++){
                int a , b;
                cin >> a >> b;
                v[a].push_back(i);
                for(int j = 1 ; j <= m ; j++)
                    dp[i][j] = b;  // 初始化时，每个节点，所有状态都是拿自己一个
            }
            creat(0);
            for(int i = 0 ; i <= n ; i ++)
                v[i].clear();
            cout << dp[0][m] << endl;
        }
        return 0;
    }

[hdoj1561The more_ The Better]: http://acm.hdu.edu.cn/showproblem.php?pid=1561