鏈接：https://ac.nowcoder.com/acm/problem/19996
來源：牛客網

題目描述
有一棵點數為N的樹，樹邊有邊權。給你一個在0~N之內的正整數K，你要在這棵樹中選擇K個點，將其染成黑色，并將其他的N-K個點染成白色。
將所有點染色后，你會獲得黑點兩兩之間的距離加上白點兩兩之間距離的和的收益。問收益最大值是多少。
輸入描述:
第一行兩個整數N,K。
接下來N-1行每行三個正整數fr,to,dis，表示該樹中存在一條長度為dis的邊(fr,to)。
輸入保證所有點之間是聯通的。N ≤ 2000,0 ≤ K ≤ N
輸出描述:
輸出一個正整數，表示收益的最大值。
示例1
輸入
復制
5 2
1 2 3
1 5 1
2 3 1
2 4 2
輸出
復制
17
說明
【樣例解釋】
將點1,2染黑就能獲得最大收益。
這種題目一看就是枚舉每條邊的貢獻。通過這道題目接觸了樹形背包。。
dp[i][j]表示著以i為根的子樹中有j個點染成黑色的最大價值。
子樹中的每個點都有兩種狀態，染色或者是不染色。所以類似于01背包。
代碼如下：

#include<bits/stdc++.h> #define ll long long #define inf 0x7f7f7f7f using namespace std;const int maxx=2e3+100; struct edge{int to,next;ll w; }e[maxx<<1]; int head[maxx<<1],tot,size[maxx]; ll dp[maxx][maxx]; int n,k; /*-------------事前準備-------------*/ inline void init() {memset(head,-1,sizeof(head));for(int i=0;i<=n;i++)for(int j=0;j<=n;j++) dp[i][j]=-inf;//初始化為負無窮大，tot=0; } inline void add(int u,int v,ll w) {e[tot].to=v,e[tot].next=head[u],e[tot].w=w,head[u]=tot++; } /*------------樹形dp-------------*/ inline void dfs(int u,int f) {size[u]=1;dp[u][0]=dp[u][1]=0;ll ans;for(int i=head[u];i!=-1;i=e[i].next){int to=e[i].to;ll w=e[i].w;if(to==f) continue;dfs(to,u);size[u]+=size[to]; for(int j=size[u];j>=0;j--)//樹形背包的模板，枚舉以u為根的子樹中染j個結點的最大值{for(int K=0;K<=size[to]&&K<=j;K++)//這j個結點中有K個在以to為節點的子樹中{ans=(ll)(K)*(k-K)+(ll)(size[to]-K)*(ll)((n-size[to]-k+K));ans*=w;ans+=dp[to][K];//還要加上子樹中已經染了K個結點的情況dp[u][j]=max(dp[u][j],dp[u][j-K]+ans);//狀態轉移方程：dp[u][j]和dp[u][j-K]+ans比較。}}} } int main() {int x,y;ll w;while(~scanf("%d%d",&n,&k)){init();for(int i=1;i<n;i++){scanf("%d%d%lld",&x,&y,&w);add(x,y,w);add(y,x,w);}dfs(1,0);printf("%lld\n",dp[1][k]);}return 0; }

努力加油a啊，(^o)/~

總結

以上是生活随笔為你收集整理的[HAOI2015]树上染色（树形dp，树形背包）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。