首页 > 代码库 > 树形DP

树形DP

2024-08-18 05:09:02   220人阅读

 给一棵节点带权的树，找到一个有k个节点的子树，求这个子树的最大权值。

 

dp[u][k]表示以u为根的子树中包含u结点的大小为k的子树的最大权和

  然后对u的每个子节点做分组背包，因为对于u的每个儿子，可以选择分配
   1,2,3...k-1个节点给它

　状态转移方程：

   当节点大小为K时，可以由根节点为u，子树大小为k-t, 加上根节点为v，子树大小为t的状态转移得到（v为u的子节点），即：


   dp[u][k] = max(dp[u][k] , dp[u][k-t]+dp[v][t]);//v是u的儿子节点

#include <iostream>  #include <cstdio>  #include <cstring>  #include <algorithm>  #include <vector>  using namespace std;//简单的树形DPint max(int a,int b){    return a>b?a:b;}const int inf = 1<<30;int n,k;int x[202];int dp[202][202];vector <int> List[202];void dfs(int u,int father){    int i,j;    for(i=0;i<List[u].size();i++)    {        int v=List[u][i];        if(v==father)             continue;        dfs(v,u);                for(j=k;j>=1;j--)//一定要倒序        {            for(int t=1;t<=j;t++)                dp[u][j]=max(dp[u][j] , dp[u][t]+dp[v][j-t]);        }    }}int main(){    scanf("%d %d",&n,&k);    int i,j,a,b;    for(i = 0;i <= n;i++) //清空list表        List[i].clear();    memset(dp,0,sizeof(dp));    dp[0][1]=0;//以0为根节点有且只有1个节点字数的最大权重    for(i=1;i<=n;i++){            scanf("%d %d",&b,&dp[i][1]);//以i为根节点有且只有1个节点字数的最大权重        List[i].push_back(b);        List[b].push_back(i);    }    k++;//多加一个0节点    dfs(0,-1);    printf("%d\n",dp[0][k]);//以0为根节点有且只有m个节点字数的最大权重    return 0;}
 
树形DP






























        

            
                
                  
                
                

                    联系

                    我们