ZOJ - 3201 Tree of Tree (树形背包)

题意：有一棵树，树上每个结点都有一个权值，求恰好包含k个结点的子树的最大权值。

设dp[i][j]为以结点i为根的树中包含j个结点的子树的最大权值，则可以把这个结点下的每棵子树中所包含的所有子树的大小当做物品的重量，对应的最大权值当做物品的价值，则相当于在它的每颗子树的所有物品中任选一个进行更新，对每个状态取最大价值。

状态转移方程：$dp[u][j]=max(dp[u][j],dp[u][j-k]+dp[v][k])$

注：由于每棵子树下只能选一件物品，所以应当先枚举状态再枚举物品，这样就避免了同一棵子树下状态的累加。

复杂度$O(n^3)$，可用siz数组确定上界优化到$O(n^2)$。

 #include<bits/stdc++.h>

 using namespace std;

 typedef long long ll;

 const int N=+;

 int hd[N],a[N],ne,n,k,dp[N][N],siz[N];

 struct E {int v,nxt;} e[N<<];

 void addedge(int u,int v) {e[ne]= {v,hd[u]},hd[u]=ne++;}

 void dfs(int u,int fa) {

     memset(dp[u],-,sizeof dp[u]);

     siz[u]=,dp[u][]=a[u];

     for(int i=hd[u]; ~i; i=e[i].nxt) {

         int v=e[i].v;

         if(v==fa)continue;

         dfs(v,u);

         for(int j=siz[u]; j>=; --j)if(~dp[u][j])

                 for(int k=; k<=siz[v]; ++k)if(~dp[v][k])

                         dp[u][j+k]=max(dp[u][j+k],dp[u][j]+dp[v][k]);

         siz[u]+=siz[v];

     }

 }

 int main() {

     while(scanf("%d%d",&n,&k)==) {

         memset(hd,-,sizeof hd),ne=;

         for(int i=; i<n; ++i)scanf("%d",&a[i]);

         for(int i=; i<n-; ++i) {

             int u,v;

             scanf("%d%d",&u,&v);

             addedge(u,v);

             addedge(v,u);

         }

         dfs(,-);

         int ans=;

         for(int i=; i<n; ++i)ans=max(ans,dp[i][k]);

         printf("%d\n",ans);

     }

     return ;

 }

巴特西

ZOJ - 3201 Tree of Tree (树形背包)

最新文章

热门文章