[DFS序上DP]一种带依赖的树上背包

Author Avatar
ZigZagK 2018年7月19日 10:00
remove_red_eye 350

题目概述

BZOJ4182弱化版,原版是要求选出来的点是连通的(我不会),弱化版只需要满足儿子选了父亲必选。

解题报告

其实之前做过带依赖的一道题,但是并没有体积,所以依然可以用正常的树形DP做。

但这道题有体积,所以原先那种复杂度分析版的树形DP就会被cao。正确姿势是在DFS序上DP,定义 \(f[i][j]\) 表示DFS序 \([1,i]\) 体积为 \(j\) 的最优解,这样转移就只有两种:

  1. \(i\) 点选,那么转移到 \(f[i+1][k]\)
  2. \(i\) 点不选,那么子树也没有选,转移到 \(f[out[i]+1][k]\)

由于物品还有个系数,所以可以二进制拆分 \(O(nmlog_2S)\) 或者单调队列(我不会)\(O(nm)\) 。第一次写写了很久QAQ,详细看代码。

示例程序

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long LL;
const int maxn=4000,maxm=4000;

int n,m,w[maxn+5],p[maxn+5],s[maxn+5];
int E,lnk[maxn+5],son[maxn+5],nxt[maxn+5];
int ti,Lt[maxn+5],Rt[maxn+5],ID[maxn+5];
LL f[maxn+5][maxm+5];

#define Add(x,y) (son[++E]=(y),nxt[E]=lnk[x],lnk[x]=E)
void Dfs(int x) {ID[Lt[x]=++ti]=x;for (int j=lnk[x];j;j=nxt[j]) Dfs(son[j]);Rt[x]=ti;}
int main(){
    freopen("shop.in","r",stdin);freopen("shop.out","w",stdout);
scanf("%d%d",&n,&m);for (int i=2,fa;i<=n;i++) scanf("%d",&fa),Add(fa,i);
for (int i=1;i<=n;i++) scanf("%d%d%d",&p[i],&w[i],&s[i]);
Dfs(1);memset(f,192,sizeof(f));LL INF=f[0][0];f[1][0]=0;
    for (int i=1,k=ID[i];i<=n;k=ID[++i]){
        for (int j=0;j<=m;j++) f[Rt[k]+1][j]=max(f[Rt[k]+1][j],f[i][j]);
        //目前f[i][j]还表示i不选的最优解,转移到out[k]+1
        for (int j=m;~j;j--) if (j>=w[k]&&f[i][j-w[k]]>=0) f[i][j]=f[i][j-w[k]]+p[k]; else f[i][j]=INF;
        //修正f[i][j],f[i][j]表示必选的最优解
        for (int t=(s[k]--,1);t<s[k];s[k]-=t,t<<=1) //因为必选,个数-1
            for (int j=m,W=t*w[k],P=t*p[k];j>=W;j--)
                f[i][j]=max(f[i][j],f[i][j-W]+P);
        if (s[k]) for (int j=m,W=s[k]*w[k],P=s[k]*p[k];j>=W;j--) f[i][j]=max(f[i][j],f[i][j-W]+P);
        //二进制拆分做多重背包
        for (int j=0;j<=m;j++) f[i+1][j]=max(f[i+1][j],f[i][j]);
        //f[i][j]已经是必选的最优解,转移到i+1
    }
    n++;for (int j=1;j<=m;j++) f[n][j]=max(f[n][j],f[n][j-1]),j>1?printf("%lld",f[n][j]):printf("%lld",f[n][j]);
    return puts(""),0;
}

本文链接:https://zigzagk.top/2018/07/19/dp-on-dfs-order
本博客所有文章除特别声明外,均采用CC BY-NC-SA 4.0 CN 许可协议。转载请注明作者和出处QwQ。