免费视频淫片aa毛片_日韩高清在线亚洲专区vr_日韩大片免费观看视频播放_亚洲欧美国产精品完整版

打開APP
userphoto
未登錄

開通VIP,暢享免費(fèi)電子書等14項(xiàng)超值服

開通VIP
Tree of tree

題意:
一棵結(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
本站僅提供存儲(chǔ)服務(wù),所有內(nèi)容均由用戶發(fā)布,如發(fā)現(xiàn)有害或侵權(quán)內(nèi)容,請(qǐng)點(diǎn)擊舉報(bào)。
打開APP,閱讀全文并永久保存 查看更多類似文章
猜你喜歡
類似文章
?LeetCode刷題實(shí)戰(zhàn)298:二叉樹最長(zhǎng)連續(xù)序列
算法連載(3)--生成最優(yōu)歸并樹
C語言實(shí)現(xiàn)哈夫曼編碼與譯碼
數(shù)據(jù)結(jié)構(gòu)_哈弗曼樹的編譯碼_課程設(shè)計(jì)_實(shí)驗(yàn)報(bào)告
Prim 算法及其高效實(shí)現(xiàn)
赫夫曼編碼
更多類似文章 >>
生活服務(wù)
分享 收藏 導(dǎo)長(zhǎng)圖 關(guān)注 下載文章
綁定賬號(hào)成功
后續(xù)可登錄賬號(hào)暢享VIP特權(quán)!
如果VIP功能使用有故障,
可點(diǎn)擊這里聯(lián)系客服!

聯(lián)系客服