P4037 [JSOI2008] 魔兽地图 题解

· · 题解

提供一种新思路

现有的大部分题解记 f[u][i][j] 为 u 装备保留 i 个给父亲，子树总花费为 j 的最大力气值。

我的状态记 f[u][i][j] 为u装备至少生产 i 个，子树总花费为 j 的最大力气值。

在操作上会复杂一些，但是感觉上可能更加直观。

先处理出 F[u][i][j] 为u装备刚好生产 i 个，子树总花费为 j 的最大力气值。

易得 \displaystyle f[u][i][j]=\max_{i\le k}F[u][k][j]，做一个关于第二维的后缀最小值顺序递推即可。

同时可以注意到，给出的图可能是森林，那么要为再为散开的树设计一个背包综合答案。

code:

#include<bits/stdc++.h>
using namespace std;
inline void rd(int &x){
    int s=0,f=1; char c=getchar();
    while(c<'0'||c>'9'){if(c=='-')f=0; c=getchar();}
    while(c>='0'&&c<='9'){s=s*10+c-48; c=getchar();}
    x=f? s:-s;
}
const int N=55,M=2e3+5,inf=1e9;
struct edge{int to,w,nt;} e[M]; int hd[N],ect;
void ade(int u,int v,int w){e[++ect]={v,w,hd[u]}; hd[u]=ect;}

int n,m,in[N],val[N],Lim[N],Cost[N];
int f[N][105][M],g[M];
//f[u][i][j] u装备生产至少 i个，总花费为 j，最大力量值 
//g[]为树上背包时的辅助转移的临时数组 
void cklp(int F[][M],int u){
    for(int i=Lim[u]-1; ~i; i--){
        for(int j=0; j<=m; j++){
            F[i][j]=max(F[i][j], F[i+1][j]);
        }
    }
}

void dfs(int u){
    memset(f[u],~63,sizeof(f[u]));
    if(!hd[u]){
        Lim[u]=min(Lim[u],m/Cost[u]);
        for(int i=0; i<=Lim[u]; i++)
            f[u][i][i*Cost[u]]=i*val[u];
        cklp(f[u], u);
        return;
    }
    Lim[u]=inf;
    for(int i=hd[u]; i; i=e[i].nt){
        int v=e[i].to, w=e[i].w;
        dfs(v);
        Lim[u]=min(Lim[u], Lim[v]/w);
        Cost[u]+=Cost[v]*w;
    }
    Lim[u]=min(Lim[u],m/Cost[u]);

    for(int i=0; i<=Lim[u]; i++){
        memset(g,~63,sizeof(g)); g[0]=0;
        for(int Ei=hd[u]; Ei; Ei=e[Ei].nt){
            int v=e[Ei].to, w=e[Ei].w;
            for(int j=m; ~j; j--){
                int t=-inf;
                for(int k=0; k<=j; k++)
                    t=max(t, f[v][i*w][k]+g[j-k]-i*w*val[v]);
                g[j]=t;
            }
        }
        for(int j=0; j<=m; j++) f[u][i][j]=g[j]+i*val[u];
    }
    cklp(f[u], u);
}

int dp[M];

signed main(){
    rd(n); rd(m);
    for(int i=1; i<=n; i++){
        rd(val[i]);
        char opt; cin>>opt;
        if(opt=='A'){
            int c; cin>>c;
            for(int j=1,v,w; j<=c; j++){
                rd(v); rd(w); ade(i,v,w);
                in[v]++;
            }
        }
        else{
            rd(Cost[i]); rd(Lim[i]);
        }
    }
    memset(dp,~63,sizeof(dp)); dp[0]=0;
    for(int i=1; i<=n; i++){
        if(in[i]) continue;
        dfs(i);
        for(int j=m; ~j; j--){
            for(int k=0; k<=j; k++){
                dp[j]=max(dp[j], dp[j-k]+f[i][0][k]);
            }
        }
    }
    int ans=0;
    for(int i=0; i<=m; i++) ans=max(ans, dp[i]);
    printf("%d\n",ans);
    return 0;
}