【算法与数据结构】——树形DP（2）

墨蓝 2022-09-07 15:45 224阅读 0赞

# 背包类树形DP #

题目地址[HDU1561][]  
题意：在一个地图上有N座城堡，每座城堡都有一定的宝物。在每次游戏中都允许攻克M个城堡并获得里面的宝物。但有些城堡不可以直接攻克，要攻克这些城堡，必须先攻克其他某个特定的城堡。计算攻克M个城堡最多可以获得的宝物数量。  
思路：背包类树形dp  
AC代码:

/* **Author:skj **Time: **Function: */
    #include <bits/stdc++.h>
    #define ll long long
    #define INF 0x3f3f3f3f
    using namespace std;
    const int N = 202;
    int a[N],b[N];
    int dp[N][N];//dp[u][i]表示从以u为根节点的树中选择i个结点能获得的最大价值
    vector<int> mm[N];
    void DFS(int u,int m)
    { 
        dp[u][1] = b[u];
        for(int i = 0;i < mm[u].size();i++)
        { 
            int v = mm[u][i];
            DFS(v,m-1);
            for(int j = m;j >= 1;j--)
            { 
                for(int k = 1;k < j;k++)
                { 
                    dp[u][j] = max(dp[u][j],dp[v][k]+dp[u][j-k]);
                }
            }
        }
    }
    int main()
    { 
    // freopen("in.txt","r",stdin);
    // freopen("out.txt","w",stdout);
        int n, m;
        while(scanf("%d%d",&n,&m)&&n)
        { 
            b[0]=0;
            for(int i = 1;i <= n;i++)
            { 
                scanf("%d%d",a+i,b+i);
                mm[a[i]].push_back(i);
            }
            DFS(0,m+1);
            printf("%d\n",dp[0][m+1]);
            for(int i = 0;i <= n;i++)
            { 
                mm[i].clear();
            }
            memset(dp,0,sizeof(dp));
        }
        return 0;
    }

# 苹果树 #

题目地址[POJ 2486][]  
题意：一棵树，只能从1号节点开始，每个节点有一定数量的苹果，走k步最多能拿到多少苹果。  
思路：树形dp，分组背包  
写了一个用vector存的树，不知道为什么一直RE，改用链式前向星就好了

/* **Author:skj **Time: **Function: */
    #include <stdio.h>
    #include <vector>
    #include <algorithm>
    #include <cstring>
    #define ll long long
    #define INF 0x3f3f3f3f
    using namespace std;
    const int N = 122;
    const int K = 222;
    int head[N];
    struct edge
    { 
        int to;
        int next;
    }E[N<<1];
    int val[N];
    int dp[N][K][2];//0:在第i个结点走k步最终不回到i结点，1：最终回到i结点
    void DFS(int u,int k,int fa)
    { 
        for(int i = 0;i <= k;i++)
        { 
            dp[u][i][0]  = dp[u][i][1] = val[u];
        }
        for(int i = head[u];i!=-1;i = E[i].next)
        { 
            int v = E[i].to;
            if(v!=fa)
            { 
                DFS(v,k,u);
                for(int j = k;j >= 1;j--)
                { 
                    for(int t = 1;t <= j;t++)
                    { 
                        dp[u][j][0] = max(dp[u][j][0],dp[u][j-t][1]+dp[v][t-1][0]);
                        if(t>=2)
                        { 
                            dp[u][j][0] = max(dp[u][j][0],dp[u][j-t][0]+dp[v][t-2][1]);
                        }
                        if(t>=2)
                        { 
                            dp[u][j][1] = max(dp[u][j][1],dp[u][j-t][1]+dp[v][t-2][1]);
                        }
                    }
                }
            }
        }
    }
    void solve()
    { 
        int n, k;
        while(scanf("%d%d",&n,&k)!=EOF)
        { 
            for(int i = 1;i <= n;i++)
            { 
                head[i] = -1;
            }
            for(int i = 1;i <= n;i++)
            { 
                scanf("%d",val+i);
            }
            for(int i = 1;i <= 2*(n-1);i+=2)
            { 
                int x, y;
                scanf("%d%d",&x, &y);
                E[i].to = y;
                E[i].next = head[x];
                head[x] = i;
    
                E[i+1].to = x;
                E[i+1].next = head[y];
                head[y] = i+1;
            }
            DFS(1,k,0);
            printf("%d\n",max(dp[1][k][0],dp[1][k][1]));
            memset(E,0,sizeof(E));
        }
    }
    
    int main()
    { 
    // freopen("in.txt","r",stdin);
    // freopen("out.txt","w",stdout);
    	int t = 1;
    // int t;
    // scanf("%d",&t);
    	while(t--)
    	{ 
    		solve();
    	}
        return 0;
    }

[HDU1561]: https://acm.hdu.edu.cn/showproblem.php?pid=1561
[POJ 2486]: http://poj.org/problem?id=2486