P4037 [JSOI2008] 魔兽地图 题解

· · 题解

题面解释：

一颗装备合成树（题目说是树，事实上 DAG 应该都一样），有购买数量限制，求出一定金额的最大力量。

思路分析：

看到题目和数据范围想到 dp。设计 ans_i 表示花费 i 元的最大力量值。但是合成关系构成树结构，为了方便维护，我们先使用树上背包预处理。设计 dp_{i,j,k} 为合成到第 i 件装备，其中 j 件继续用于合成，已经花了 k 元的最大力量。

对于叶子节点，直接购买，是经典的背包问题。对于非叶子节点，我们将他被合成 1 个的最小代价抽象成购买他的代价，然后处理出其购买上限。然后根据合成途径进行转移，转移部分在代码注释中很详细了。

由于设计状态时为一共获得的总力量，我们只需要在遍历后对根节点进行背包，根节点一定不用于合成，所以直接以 dp_{rt,0,k}(k\in[0,m]) 进行转移。

时间复杂度似乎不对，但应该没有更优做法了，是完全跑不满的，可以轻松通过。

AC Code:

并非自己独立完成，借鉴过其他题解，思路一样。但是调试与理解后，详细进行注释，帮助后人更好地理解 dp 过程。

#include<bits/stdc++.h>
using namespace std;
const int N=60,M=2e3+10;
bool vis[N];struct node{int to,val;};vector<node>g[N];
int n,m,dp[N][N*2][M],p[M],a[N],c[N],z[N],in[N],ans[M];
void dfs(int u){
    if(vis[u])return;vis[u]=1;
    if(g[u].empty()){
        //直接购买 
        z[u]=min(z[u],m/c[u]);
        for(int i=z[u];i>=0;i--)//多少用来合成 
            for(int j=i;j<=z[u];j++)//总共买多少 
                dp[u][i][j*c[u]]=a[u]*(j-i);
        return;
    }
    //合成 
    for(auto v:g[u]){
        dfs(v.to);
        z[u]=min(z[u],z[v.to]/v.val);
        c[u]+=v.val*c[v.to];
    }
    z[u]=min(z[u],m/c[u]);
    //处理消耗与数量限制 
    for(int i=z[u];i>=0;i--){//合成i个u 
        memset(p,0xcf,sizeof(p));p[0]=0;
        //p[i]表示合成i个u花了k元子孙节点可以提供多少防御 
        for(auto v:g[u]){
            for(int j=m;j>=0;j--){//到当前节点一共花费 
                int res=dp[0][0][0];
                for(int k=0;k<=j;k++)//当前节点花费 
                    res=max(res,p[j-k]+dp[v.to][i*v.val][k]);    
                p[j]=res;
            }
        }
        for(int j=0;j<=i;j++)//多少个装备用来合成更高级的 
            for(int k=0;k<=m;k++)//花了多少钱 
                dp[u][j][k]=max(dp[u][j][k],p[k]+a[u]*(i-j));
    }
} 
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin>>n>>m;
    memset(z,0x3f,sizeof(z));
    for(int i=1,t,v,w;i<=n;i++){
        char ch;cin>>a[i]>>ch;
        if(ch=='A'){
            cin>>t;while(t--)
            cin>>v>>w,in[v]++,
            g[i].push_back({v,w});
        }else cin>>c[i]>>z[i];
    }
    //dp[i][j][k]表示i装备j个用来合成花费了k元的最大力量 
    //ans[i]表示花费i元可以获得最大力量 
    memset(dp,0xcf,sizeof(dp));
    for(int i=1;i<=n;i++)if(!in[i]){
        dfs(i);
        for(int j=m;j>=0;j--)//总共花了多少钱 
            for(int k=0;k<=j;k++)//此树花多少钱 
                ans[j]=max(ans[j],ans[j-k]+dp[i][0][k]);//根节点不上传 
    }
    cout<<ans[m];
    return 0;
}