POJ-1155 TELE 树形背包dp

佚名 6年前 (2019-04-17) 随笔 567人围观抢沙发百度已收录

dp[u][i]代表以u为根的子树选i个叶子的最大收益

那么dp[u][i]=max(dp[u][i],dp[v][k]+dp[u][i-k]-len) (1=<k<=i)

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

细节看代码：

#include<iostream>
#include<cstdio>
#include<vector>
#include<cstring>
using namespace std;
const int N=3e3+10;
int n,m,leaf[N],v[N],dp[N][N];
vector<int> G[N],E[N];

int dfs1(int x) {
    if (G[x].size()==0) return leaf[x]=1;
    leaf[x]=0;
    for (int i=0;i<G[x].size();i++) {
        int y=G[x][i];
        leaf[x]+=dfs1(y);
    }
    return leaf[x];
}

void dfs2(int x) {
    if (v[x]) dp[x][1]=v[x];
    dp[x][0]=0;
    for (int i=0;i<G[x].size();i++) {
        int y=G[x][i],len=E[x][i];
        
        dfs2(y);
        
        for (int j=leaf[x];j;j--)
            for (int k=0;k<=leaf[y];k++)
                dp[x][j]=max(dp[x][j],dp[y][k]+dp[x][j-k]-len);
    }
}

int main()
{
    int n,m; cin>>n>>m;
    for (int i=1;i<=n-m;i++) {
        int t,x,y; cin>>t;
        for (int j=1;j<=t;j++) {
            scanf("%d%d",&x,&y);
            G[i].push_back(x);
            E[i].push_back(y);
        }
    }
    dfs1(1);
    for (int i=n-m+1;i<=n;i++) scanf("%d",&v[i]);
    memset(dp,-0x3f,sizeof(dp));
    dfs2(1);
    int ans=0;
    for (int i=0;i<=leaf[1];i++) if (dp[1][i]>=0) ans=i;
    cout<<ans<<endl;
    return 0;
}