題意:
一棵結(jié)點(diǎn)帶權(quán)樹,大小(結(jié)點(diǎn)數(shù))為k的子樹的權(quán)值和最大為多少。
初步分析
這道題其實(shí)就是一道01背包問題只是是在樹上做而已。背包的總?cè)萘烤褪莐個(gè)結(jié)點(diǎn)(一定得剛好裝滿),每個(gè)物品的價(jià)值就是結(jié)點(diǎn)的權(quán)值w[i].注意,并不是隨便選取結(jié)點(diǎn)就行了。而是一定得是子樹。那么這一點(diǎn)我們要怎么實(shí)現(xiàn)呢。首先我們用dp[i][j]來表示以結(jié)點(diǎn)i為首的結(jié)點(diǎn)數(shù)為j的權(quán)值最大的一棵子樹。那么dp[i][j]的狀態(tài)方程怎么寫呢?dp[i][j]=max(dp[i][j],dp[i][j-w] dp[v][w])(v是結(jié)點(diǎn)i的子節(jié)點(diǎn),1=<j<=cnt[i],0<w<j)注意我們是怎么保證dp[i][j]表示的是以結(jié)點(diǎn)i為首的子樹呢?新節(jié)點(diǎn)所能取得的最大結(jié)點(diǎn)數(shù)只能是j-1,因?yàn)閐p[i][1]始終代表的是結(jié)點(diǎn)i,所以才能保證都是以結(jié)點(diǎn)i為首的子樹。而且由于是01背包所以我們的背包容量j從大到小更新,這樣保證所有的小值都是上一次子節(jié)點(diǎn)的更新值而不是重復(fù)使用當(dāng)前結(jié)點(diǎn)的值(不然的話就變成完全背包了)。
直接上代碼
#include <iostream>#include <string.h>using namespace std;const int MAX_N=110;const int MAX_M=220;int w[MAX_N];int dp[MAX_N][MAX_N];int cnt[MAX_N];int n,k,answer=0;//我們這里用圖來儲(chǔ)存樹,在遍歷的時(shí)候通過一個(gè)father參數(shù)就可以轉(zhuǎn)化為樹了。沒有必要用一個(gè)father數(shù)組來儲(chǔ)存int ans=0;int head[MAX_N];struct edge{ int v; int next;}eid[MAX_M];void insert(int u,int v){ eid[ans].v=v; eid[ans].next=head[u]; head[u]=ans ;}int read(){ int w=1,s=0; char ch=getchar(); while(!isdigit(ch)){ if(ch=='-'){ w*=-1; } ch=getchar(); } while(isdigit(ch)){ s=(s<<1) (s<<3) ch-48; ch=getchar(); } return s*w;}int dfs(int node,int father){ cnt[node]=1; for(int i=head[node];i!=-1;i=eid[i].next){ int v=eid[i].v; if(v==father) continue; cnt[node] =dfs(v,node); } dp[node][1]=w[node]; for(int i=head[node];i!=-1;i=eid[i].next){ int v=eid[i].v; if(v==father) continue; for(int j=cnt[node];j>=1;--j) { for (int m = 0; m <=cnt[v] && m<j ; m) { dp[node][j] = max(dp[node][j], dp[node][j - m] dp[v][m]); } } } answer=max(answer,dp[node][k]); return cnt[node];}int main() { while(scanf("%d %d",&n,&k)!=EOF) { for (int i = 1; i <= n; i) { w[i] = read(); } memset(head, -1, sizeof(head)); ans=0; for (int i = 0; i <MAX_N; i) { for (int j = 0; j <MAX_N; j) { dp[i][j] = 0; } } for (int i = 1; i <= n - 1; i) { int x, y; x = read() 1; y = read() 1; insert(x, y); insert(y, x); } dfs(1, -1); cout <<answer<<endl; answer=0; } return 0;}
來源:https://www.icode9.com/content-4-386351.html
聯(lián)系客服