P4037 魔兽地图 题解

· · 题解

[JSOI2008]魔兽地图

 某机房dp巨佬（%%%%%%%钛强了）给了我这道题，想了一节物理课出了点思路（物理课总是灵感的源泉）,被dalao不是很看好。坚持写出来后复杂度没错但是常数巨大，被卡到了60分……

 优化一年后终于过了这道题，发现和题解思路不大一样（明示我思路清奇？），于是写了这篇题解记录一下。

 （本题解和其他题解思路有些差异，因此导致卡常比较严重，可供学习参考，也是提供另一种思路）

题意分析

 题目说明了合成过程是一棵树。所以一看就觉得是一道树上背包，仔细一看会发现有一些限制，而代价是在叶子节点上的。

 处理的话稍加思考就能想到要从底层往上合成，再将合成完本层剩下的钱最优化分到下层，这就是大体上的思想了。

解法

 首先考虑将下一层的装备合成父亲不一定是最优的（显而易见），但是合成父亲的父亲可能是血赚的。

 而如果为了本层最优不合成本层的装备，不一定能满足合成上层装备的要求，即本成合成的装备数是会对上层产生影响的。

 对于这种问题，我们充分运用朴素（暴力）的思想，把本层合成的装备数也压成一维dp就好了……

 所以我们定义 dp_{i,j,k} 为对于第x种装备，分到了j的钱，造了i个x以后剩下的钱分到子树中能产生的最大价值

 （这里是不算x的价值的，因为有的x可能是中间产物，被造成了更高级的装备，它本身的价值是不需要被计算的）

 然后考虑转移的过程，本层和下层钱数确定后，本层要造i个装备，所以下面几层至少要造 i \cdot num 个(num为造一个x需要的下层y的个数），我们遍历一遍用来更新dp数组就可以了。

 这样我们就得到了一个 O(nm^2v^2)（数量限制为v）的算法，虽然说跑不满，但是毫无疑问，会被卡掉……

 再考虑一下当本层和下层钱数确定后，如果下层个数是递减遍历的，那么对于一个能满足较大本层个数i的下层个数j，它一定还能满足下一个较小的i。

 所以只需要记录一个变量now为能满足当前本层个数i的最优的下层贡献即可。

 实际处理过程中即为从大到小遍历一遍下层个数，一遍遍历一遍更新now，然后用now去更新dp就可以了。

 这样我们缩掉了一个v，实际的复杂度是 O(nm^2v) 的。这也是一个 复 杂 度 正确的算法。

 实现一下就得到代码：

#include<cstdio>
#include<vector>
#include<cstring>
#include<cstdlib>
using namespace std;
#define INF 1145141919
struct edge
{
    int to,wei;
    edge(){}
    edge(int to,int wei):to(to),wei(wei){}
};
int n,m,dp[52][101][2001],w[52],c,in1,in2,lim[52],ans,mig[52];
vector<edge>ed[52];
char in;
bool vis[52],yd[52];
int minn(int x,int y)
{
    return x<=y?x:y;
}
int maxx(int x,int y)
{
    return x>=y?x:y;
}
void dfs(int x)
{
    vis[x]=true;
    if(yd[x])
    {
        for(int i=0;i<=m;i++)
        {
            for(int j=0;j<=lim[x];j++)
            {
                if(w[x]*j<=i)dp[x][j][i]=0;
            }
        }
        return;
    }
    lim[x]=100;
    for(vector<edge>::iterator ite=ed[x].begin();ite!=ed[x].end();ite++)
    {
        if(!vis[ite->to])dfs(ite->to);
        lim[x]=minn(lim[x],lim[ite->to]/ite->wei);
        w[x]+=w[ite->to]*ite->wei;
    }
    for(int i=0;i<=lim[x];i++)
    {
        for(int j=0;j<=m;j++)
        {
            dp[x][i][j]=0;
        }
    }
    for(vector<edge>::iterator ite=ed[x].begin();ite!=ed[x].end();ite++)
    {
        for(int i=m;i>0;i--)
        {
            for(int j=i;j>0;j--)
            {
                int now=-INF;
                for(int k=lim[ite->to];k>=0;k--)
                {
                    if(dp[ite->to][k][j]<0)continue;
                    if(j>=w[ite->to]*k)now=maxx(now+mig[ite->to],dp[ite->to][k][j]);
                    int hh=k/ite->wei;
                    if(hh<=lim[x]&&i>=hh*w[x]&&i-j>=hh*w[x]-w[ite->to]*k)dp[x][hh][i]=maxx(dp[x][hh][i],dp[x][hh][i-j]+now);
                }
            }
        }
    }
    for(int i=0;i<=lim[x];i++)
    {
        ans=maxx(ans,dp[x][i][m]+mig[x]*i);
    }
}
int main()
{
    scanf("%d %d",&n,&m);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&mig[i]);
        in=getchar();
        while(in!='A'&&in!='B')
        {
            in=getchar();
        }
        if(in=='A')
        {
            scanf("%d",&c);
            for(int j=1;j<=c;j++)
            {
                scanf("%d%d",&in1,&in2);
                ed[i].push_back(edge(in1,in2));
            }
        }
        else
        {
            yd[i]=true;
            scanf("%d%d",&w[i],&lim[i]);
        }
    }
    for(int i=1;i<=n;i++)
    {
        if(!vis[i])dfs(i);
    }
    printf("%d",ans);
    return 0;
}

 自信交上去……

 以正解16倍的大常数被卡掉了……

 是我们的优化就开始了……

 主要可以优化的部分是i,j,k的三重for循环，我们可以通过判断去掉一部分无用的状态，缩小常数。

 无用的状态有三种：

  1.当要造儿子y的个数k与儿子y的花费之积超过了分给儿子y的钱数j时，很明显它是没有意义的，不需要更新now，不需要更新dp。

  2.当要造x的个数与x的花费之积超过了x分到的钱数i时，这时的的状态也是没有意义的，不需要更新dp。

  3.当要造k个x，分到其他儿子的钱数i-j，小于其他儿子至少要分到的钱时，这个j本身可能是有意义的，需要更新now，但对i是没有意义的，不能更新dp。

 考虑i,j的状态数是远大于k的状态数的，如果保持先i后j再k的循环顺序，剪枝的效率是很低的，因此我们要把k提到循环的前面。

 先将k提到j之前，对于j不同的情况，now是不能共用的，因为分到不同钱数，造k个儿子j的dp值是不同的。

 所以我们将now扩展一维，分别记录不同j下的now，由此将k提到j外面。

 另外考虑状态，将j分为两种情况，对于满足上述情况3的j，只用来更新now，满足情况1的j直接剪掉。

 于是我们又得到了一份代码：

#include<cstdio>
#include<vector>
#include<cstring>
#include<cstdlib>
using namespace std;
#define INF 1145141919
struct edge
{
    int to,wei;
    edge(){}
    edge(int to,int wei):to(to),wei(wei){}
};
int n,m,dp[52][101][2001],w[52],c,in1,in2,lim[52],ans,mig[52],ccn,now[2001];
vector<edge>ed[52];
char in;
bool vis[52],yd[52];
int minn(int x,int y)
{
    return x<=y?x:y;
}
int maxx(int x,int y)
{
    return x>=y?x:y;
}
void dfs(int x)
{
    vis[x]=true;
    if(yd[x])
    {
        return;
    }
    lim[x]=100;
    for(vector<edge>::iterator ite=ed[x].begin();ite!=ed[x].end();ite++)
    {
        if(!vis[ite->to])dfs(ite->to);
        lim[x]=minn(lim[x],lim[ite->to]/ite->wei);
        w[x]+=w[ite->to]*ite->wei;
    }
    for(vector<edge>::iterator ite=ed[x].begin();ite!=ed[x].end();ite++)
    {
        for(int i=m;i>0;i--)
        {
            memset(now,0xcf,sizeof(now));
            for(int k=lim[ite->to];k>=0;k--)
            {
                int xxx=w[ite->to]*k,hh=k/ite->wei,yyy=i-hh*w[x]+w[ite->to]*k;
                for(int j=i;j>yyy&&j>=xxx;j--)
                {
                    now[j]=maxx(now[j]+mig[ite->to],dp[ite->to][k][j]);
                }
                for(int j=minn(yyy,i);j>=xxx;j--)
                {
                    now[j]=maxx(now[j]+mig[ite->to],dp[ite->to][k][j]);
                    dp[x][hh][i]=maxx(dp[x][hh][i],dp[x][hh][i-j]+now[j]);
                }
            }
        }
    }
    for(int i=0;i<=lim[x];i++)
    {
        ans=maxx(ans,dp[x][i][m]+mig[x]*i);
    }
}
int main()
{
    scanf("%d %d",&n,&m);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&mig[i]);
        in=getchar();
        while(in!='A'&&in!='B')
        {
            in=getchar();
        }
        if(in=='A')
        {
            scanf("%d",&c);
            for(int j=1;j<=c;j++)
            {
                scanf("%d%d",&in1,&in2);
                ed[i].push_back(edge(in1,in2));
            }
        }
        else
        {
            yd[i]=true;
            scanf("%d%d",&w[i],&lim[i]);
        }
    }
    for(int i=1;i<=n;i++)
    {
        if(!vis[i])dfs(i);
    }
    printf("%d",ans);
    return 0;
}

 不自信地交上去，果然，又T了……

 好歹又过了一个点，有点进步（自我安慰）。

 然后考虑怎么将k提到i之前……

 根据最开始的定义，我们可以发现，now只与j和k有关，它记录的是下一层的东西，实际上是和i没有关系的

 所以我们可以直接将now提到三重for循环外单独处理，将now再扩展一维，记录同样j,k下最优的now

 （这时的now已经可以认为是单独一个dp的内容了，它记录的是下层的儿子y分到j的钱数，先造k个y，再将剩下的钱自由分配，可以分配给子树，也可以再造几个y，不算最开始造的k个y能创造的最大价值）

 这时的i,j,k已经是无所谓顺序的了（只需要保证i递减（背包），状态有意义），我们可以肆意地将k提到最外层，然后将满足前面情况1,2,3的状态全部剪掉。

 另外此时的 now_{k,j} 在j相同时，对于k递减一定是单调递增的。所以对于满足 i\cdot num \leq k < (i+1)\cdot num 的所有k中，k=i\cdot num 是最优的。

 因此只需要不需要遍历所有k，只需要遍历一遍i用最优的k更新答案就可以了。

 由此我们得到了最终代码：

代码

#include<cstdio>
#include<vector>
#include<cstring>
#include<cstdlib>
using namespace std;
#define INF 1145141919
struct edge
{
    int to,wei;
    edge(){}
    edge(int to,int wei):to(to),wei(wei){}
};
int n,m,dp[52][101][2001],w[52],c,in1,in2,lim[52],ans,mig[52],ccn,now[102][2001];
vector<edge>ed[52];
char in;
bool vis[52],yd[52];
int minn(int x,int y)
{
    return x<=y?x:y;
}
int maxx(int x,int y)
{
    return x>=y?x:y;
}
void dfs(int x)
{
    vis[x]=true;
    if(yd[x])
    {
        return;
    }
    lim[x]=100;
    for(vector<edge>::iterator ite=ed[x].begin();ite!=ed[x].end();ite++)
    {
        if(!vis[ite->to])dfs(ite->to);
        lim[x]=minn(lim[x],lim[ite->to]/ite->wei);
        w[x]+=w[ite->to]*ite->wei;
    }
    //预处理本装备一件的造价和数量的上限。
    for(vector<edge>::iterator ite=ed[x].begin();ite!=ed[x].end();ite++)
    {
        memset(now,0xcf,sizeof(now));
        for(int k=lim[ite->to];k>=0;k--)
        {
            int yyy=k*w[ite->to];
            for(int i=m;i>=yyy;i--)
            {
                now[k][i]=maxx(now[k+1][i]+mig[ite->to],dp[ite->to][k][i]);
            }
        }
        //对每个儿子先处理出now。
        for(int k=0;k<=lim[x];k++)
        {
            int xxx=w[ite->to]*k*ite->wei,zzz=w[x]*k;
            for(int i=m;i>=zzz;i--)
            {
                int yyy=i-k*w[x]+w[ite->to]*k*ite->wei;
                for(int j=minn(i,yyy);j>=xxx;j--)
                {
                    dp[x][k][i]=maxx(dp[x][k][i],dp[x][k][i-j]+now[k*ite->wei][j]);
                }
            }
        }
        //对可行的状态更新dp。
    }
    for(int i=0;i<=lim[x];i++)
    {
        ans=maxx(ans,dp[x][i][m]+mig[x]*i);
    }
    //因为懒得找根就直接对节点更新答案了。
}
int main()
{
    scanf("%d %d",&n,&m);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&mig[i]);
        in=getchar();
        while(in!='A'&&in!='B')
        {
            in=getchar();
        }
        if(in=='A')
        {
            scanf("%d",&c);
            for(int j=1;j<=c;j++)
            {
                scanf("%d%d",&in1,&in2);
                ed[i].push_back(edge(in1,in2));
            }
        }
        else
        {
            yd[i]=true;
            scanf("%d%d",&w[i],&lim[i]);
        }
    }
    //分情况输入装备的情况。
    for(int i=1;i<=n;i++)
    {
        if(!vis[i])dfs(i);
    }
    //因为懒得找根就直接dfs了。
    printf("%d",ans);
    //输出。
    return 0;
}

 于是终于AC了……

end