一类有依赖的树形背包dp方法

时间：2020-12-25 05:59:06

失踪人口回归系列 这个标题是不是看起来很厉害呢233

给一道例题：有一个树，每一个节点代表一个物品，每个物品有重量和价值，每个物品必须先选父亲才能选自己。求给定重量内最大价值。

这题的思路十分的厉害。我们把树的dfs序建出来，对于dfs序上每一个点，我们考虑如果自己选那么自己子树内就可以选，否则只有在这棵子树外面才可以选。

那么我们记f[i][j]为dfs序中第i个点及以后的dfs序大小为j的联通块的最大权值，所以我们可以得出f[i][j]=max(f[i+1][j-w[i]]+v[st[i]],f[i+sz[st[i]]][j])类似这样。

#include <iostream>

#include <stdio.h>

#include <stdlib.h>

#include <string.h>

#include <memory.h>

using namespace std;

//w=weight v=value

#define SZ 5004

int n,m,fa[SZ],w[SZ],v[SZ],fc[SZ],nc[SZ],md[SZ],siz[SZ],dp[SZ][SZ];

int st[SZ],t=,dl[SZ];

void ass(int x) {int f=fa[x]; if(f) nc[x]=fc[f], fc[f]=x;}

void dfs(int p)

{

    siz[p]=; st[p]=++t; dl[t]=p;

    for(int c=fc[p];c;c=nc[c])

    {

        dfs(c); siz[p]+=siz[c];

    }

}

#define FO(x) {freopen(#x".in","r",stdin); freopen(#x".out","w",stdout);}

int main()

{

    scanf("%d%d",&n,&m);

    for(int i=;i<=n;i++) scanf("%d%d%d",fa+i,w+i,v+i), ass(i);

    dfs();

    for(int p=;p<=m;p++) dp[n+][p]=dp[n+][p]=-;

    dp[n+][]=; //原来这里忘了写

    for(int i=n;i>=;i--)

    {

        int x=dl[i];

        for(int p=;p<=m;p++)

        {

            if(p<w[x]) dp[i][p]=max(dp[i+siz[x]][p],);

            else dp[i][p]=max(max(dp[i+siz[x]][p],dp[i+][p-w[x]]+v[x]),);

        }

    }

    printf("%d\n",dp[][m]);

}

UPD：发现一个bug，已修复，详见注释

相关文章