4033: [HAOI2015]樹(shù)上染色

Time Limit: 10 Sec??Memory Limit: 256 MB
Submit: 2437??Solved: 1034
[Submit][Status][Discuss]

Description

有一棵點(diǎn)數(shù)為N的樹(shù)，樹(shù)邊有邊權(quán)。給你一個(gè)在0~N之內(nèi)的正整數(shù)K，你要在這棵樹(shù)中選擇K個(gè)點(diǎn)，將其染成黑色，并 將其他的N-K個(gè)點(diǎn)染成白色。將所有點(diǎn)染色后，你會(huì)獲得黑點(diǎn)兩兩之間的距離加上白點(diǎn)兩兩之間距離的和的收益。 問(wèn)收益最大值是多少。

Input

第一行兩個(gè)整數(shù)N,K。 接下來(lái)N-1行每行三個(gè)正整數(shù)fr,to,dis，表示該樹(shù)中存在一條長(zhǎng)度為dis的邊(fr,to)。 輸入保證所有點(diǎn)之間是聯(lián)通的。 N<=2000,0<=K<=N

Output

輸出一個(gè)正整數(shù)，表示收益的最大值。

Sample Input

5 2
1 2 3
1 5 1
2 3 1
2 4 2

Sample Output

17
【樣例解釋】
將點(diǎn)1,2染黑就能獲得最大收益。

HINT

2017.9.12新加數(shù)據(jù)一組 By?GXZlegend

Source

鳴謝bhiaibogf提供

[Submit][Status][Discuss]

初看此題，樹(shù)上背包！f[i][j]表示以i為根的子樹(shù)選j個(gè)黑點(diǎn)的最大收益！

然后就發(fā)現(xiàn)轉(zhuǎn)移爆炸。

于是令f[i][j]表示以i為根的子樹(shù)選j個(gè)黑點(diǎn)的貢獻(xiàn)，合并子樹(shù)貢獻(xiàn)后將自己到父親的邊的貢獻(xiàn)加上即可，轉(zhuǎn)移一句話。

然后就沒(méi)了？

回頭一看發(fā)現(xiàn)復(fù)雜度是$O(n^3)$的，于是分析一波復(fù)雜度。

$T(n)=\sum_{u=1}^{n}\sum_{v,w\ is\ a\ son\ of\ u} size[v]\times size[w]=\sum_{u=1}^{n}\sum_{u\ is\ the\ LCA\ of\ v,w} 1=O(n^2)$

于是就可做了，當(dāng)然如果寫(xiě)丑了還是會(huì)變成$O(n^3)$的。

最后要記得邊長(zhǎng)是long long，狂WA不止。

1 #include<cstdio> 2 #include<cstring> 3 #include<algorithm> 4 #define rep(i,l,r) for (int i=l; i<=r; i++) 5 #define For(i,x) for (int i=h[x],k; i; i=nxt[i]) 6 typedef long long ll; 7 using namespace std; 8 9 const int N=2010; 10 int n,m,u,v,w,cnt,h[N],sz[N],to[N<<1],nxt[N<<1]; 11 ll f[N][N],dep[N],val[N<<1]; 12 void add(int u,int v,int w){ to[++cnt]=v; val[cnt]=w; nxt[cnt]=h[u]; h[u]=cnt; } 13 14 void dfs(int x,int fa){ 15 f[x][0]=f[x][1]=0; sz[x]=1; 16 For(i,x) if ((k=to[i])!=fa){ 17 dep[k]=val[i]; dfs(k,x); 18 for (int l=min(sz[x],m); l>=0; l--) 19 for (int j=min(sz[k],m-l); j>=0; j--) f[x][j+l]=max(f[x][j+l],f[x][l]+f[k][j]); 20 sz[x]+=sz[k]; 21 } 22 rep(i,0,min(sz[x],m)) f[x][i]+=dep[x]*(i*(m-i)+(sz[x]-i)*(n-sz[x]-m+i)); 23 } 24 25 int main(){ 26 freopen("bzoj4033.in","r",stdin); 27 freopen("bzoj4033.out","w",stdout); 28 scanf("%d%d",&n,&m); 29 memset(f,-0x3f,sizeof(f)); 30 rep(i,2,n) scanf("%d%d%d",&u,&v,&w),add(u,v,w),add(v,u,w); 31 dfs(1,0); printf("%lld\n",f[1][m]); 32 return 0; 33 }

?

轉(zhuǎn)載于:https://www.cnblogs.com/HocRiser/p/8757555.html

總結(jié)

以上是生活随笔為你收集整理的[BZOJ4033][HAOI2015]树上染色(树形DP)的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。