POJ-2486 Apple Tree 树形DP

朴灿烈づ我的快乐病毒、 2021-12-05 04:41 256阅读 0赞

题意：一棵n个点的树，每个点有苹果数vi，每条边长度为1。从树根1出发，你不能走多于m步，走到一个点就能获得该点苹果，问能获得最多苹果是多少个？

解法：这道题想了挺久的还是没想到只能看题解了。很经典的树形DP了。

很容易想到设dp\[x\]\[j\]表示x子树分配j步能获得最多苹果数量，但是这样是不够的，因为很容易发现只有哪些回到了x点的方案的代价才是子树大小\*2，但是走到最后的时候其实可以不用回到x点。那么我们就增加状态纬度，设dp\[i\]\[j\]\[0/1\]:给树i**恰好**分配j步(回/不回来)i点的最大值。然后分3中情况写状态转移方程：

因为我们是一边遍历儿子一边做背包，所以在遍历当前y子树的时候，dp\[x\]可以看成是左边子树结果集，dp\[y\]就是当前子树结果集，状态转移方程其实就是想办法把这两个结果集结合在一起。那么其实就三种情况：左边回来且现在回来，走边回来走到右边之后不回来了，右边回来走到左边之后不回来了

dp\[x\]\[j\]\[0\]=max(dp\[x\]\[j\]\[0\],dp\[x\]\[j-k\]\[0\]+dp\[y\]\[k-2\]\[0\]);   //情况①：表示遍历从左边的子树回来x点之后，去y子树，再回来x点。

dp\[x\]\[j\]\[1\]=max(dp\[x\]\[j\]\[1\],dp\[x\]\[j-k\]\[0\]+dp\[y\]\[k-1\]\[1\]);  //情况②：表示从左边回来，去y子树，不回来x点了

dp\[x\]\[j\]\[1\]=max(dp\[x\]\[j\]\[1\],dp\[x\]\[j-k\]\[1\]+dp\[y\]\[k-2\]\[0\]);  //情况3：表示从y子树回来，去左边，不回来x点了

写了这三种情况就可以AC了。这里提一个小细节，网上很多代码dp\[x\]\[j\]\[0/1\]代表的是给x树分配小于等于j步的最大价值，博主写的是恰好分配j步，这点不同在代码会有小小的不同。

总的来说，感觉这道题还是不容易想到，首先得有经验发现状态不够时增加一个\[0/1\]纬度表示，然后的写出正确的状态转移方程才能写对，也只能多做题才能有感觉吧。

#include<iostream>
    #include<cstdio>
    #include<cstring>
    #include<vector>
    using namespace std;
    const int N=1e2+10;
    int n,m,v[N];
    vector<int> G[N];
    
    int dp[N][N<<1][2];  //dp[i][j][0/1]:给树i分配j步(回/不回来)i点的最大值 
    void dfs(int x,int fa) {
        for (int i=0;i<G[x].size();i++) {
            int y=G[x][i];
            if (y==fa) continue;
            dfs(y,x);
            for (int j=m;j>=0;j--) {  //计算dp[x][j] 
                for (int k=1;k<=j;k++) {  //给儿子y分配k步 
                    if (k>=2) dp[x][j][0]=max(dp[x][j][0],dp[x][j-k][0]+dp[y][k-2][0]);
                    if (k>=1) dp[x][j][1]=max(dp[x][j][1],dp[x][j-k][0]+dp[y][k-1][1]);
                    if (k>=2) dp[x][j][1]=max(dp[x][j][1],dp[x][j-k][1]+dp[y][k-2][0]);
                }
            }
        }
    }
    
    int main()
    {
        while (scanf("%d%d",&n,&m)==2) {
            for (int i=1;i<=n;i++) G[i].clear();
            memset(dp,-0x3f,sizeof(dp));
            for (int i=1;i<=n;i++) scanf("%d",&v[i]),dp[i][0][0]=dp[i][0][1]=v[i];
            for (int i=1;i<n;i++) {
                int x,y; scanf("%d%d",&x,&y);
                G[x].push_back(y);
                G[y].push_back(x);
            }
            dfs(1,0);
            int ans=0; 
            for (int i=0;i<=m;i++) ans=max(ans,max(dp[1][i][0],dp[1][i][1]));
            printf("%d\n",ans);
        }
        return 0;
    }

转载于:https://www.cnblogs.com/clno1/p/11191652.html