HihoCoder - 1055 树形dp

vj链接：https://vjudge.net/contest/367007#problem/G

题意：

给你一棵树，树上有n个节点，每一个节点有一个权值，树根节点是1，你需要找到以1为起点连通的m个点的最大的权值（连通的意思也就是：这m个点在从1点遍历树的时候，有这样的一个序列）

题解：

dp[x][i]表示：以x为起点，连通量为i的最大权值

dp转移方程：

for(int i=m;i>1;--i)  //因为每一个节点只能用一次，所以要像01背包一样循环

            {

                for(int j=0;j<i;++j)

                {

                    dp[x][i]=max(dp[x][i],dp[x][i-j]+dp[v][j]); //v就是这条边的终点

                }

            }

因为我们要求dp[1][m]所以我们要先找到子树节点的dp值，然后由子树结点的值去求出来根节点的最优值

这个dp的过程也类似于背包容量为m的01背包

代码：

 1 #include<stdio.h>

 2 #include<string.h>

 3 #include<iostream>

 4 #include<algorithm>

 5 #include<math.h>

 6 #include<vector>

 7 #include<queue>

 8 #include<stack>

 9 #include<map>

10 using namespace std;

11 typedef long long ll;

12 const int maxn=105;

13 const int INF=0x3f3f3f3f;

14 const double eps=1e-8;

15 const double PI=3.1415926;

16 const int mod = 1e9+7;

17 int val[maxn],dp[maxn][maxn];

18 int n,m;

19 vector<int>w[maxn];

20 void dfs(int x,int pre)  //x代表起点

21 {

22     dp[x][1]=val[x];

23     for(int i=0;i<w[x].size();++i)  //这个相当于背包dp枚举物品那一层for循环

24     {

25         int v=w[x][i];

26         if(v!=pre)

27         {

28             dfs(v,x);

29             for(int i=m;i>1;--i)  //因为每一个节点只能用一次，所以要像01背包一样循环

30             {

31                 for(int j=0;j<i;++j)

32                 {

33                     dp[x][i]=max(dp[x][i],dp[x][i-j]+dp[v][j]);

34                 }

35             }

36         }

37     }

38 }

39 int main()

40 {

41     scanf("%d%d",&n,&m);

42     for(int i=1;i<=n;++i)

43         scanf("%d",&val[i]);

44     for(int i=1;i<n;++i)

45     {

46         int x,y;

47         scanf("%d%d",&x,&y);

48         w[x].push_back(y);

49         w[y].push_back(x);

50     }

51     dfs(1,0);

52     printf("%d\n",dp[1][m]);

53     return 0;

54 }

巴特西

HihoCoder - 1055 树形dp

最新文章

热门文章