[BZOJ1017/Luogu4037][JSOI2008]魔兽地图DotR(动态规划)

发布于 2018-04-08  65 次阅读


本文章由SYCstudio或本站其它作者所有,严禁转载,转载必究

本文链接地址:[BZOJ1017/Luogu4037][JSOI2008]魔兽地图DotR(动态规划)

Description

DotR (Defense of the Robots) Allstars是一个风靡全球的魔兽地图,他的规则简单与同样流行的地图DotA(Defense of the Ancients) Allstars。DotR里面的英雄只有一个属性——力量。他们需要购买装备来提升自己的力量值,每件装备都可以使佩戴它的英雄的力量值提高固定的点数,所以英雄的力量值等于它购买的所有装备的力量值之和。装备分为基本装备和高级装备两种。基本装备可以直接从商店里面用金币购买,而高级装备需要用基本装备或者较低级的高级装备来合成,合成不需要附加的金币。装备的合成路线可以用一棵树来表示。比如,Sangeand Yasha的合成需要Sange,Yasha和Sange and Yasha Recipe Scroll三样物品。其中Sange又要用Ogre Axe, Belt of Giant Strength和 Sange Recipe Scroll合成。每件基本装备都有数量限制,这限制了你不能无限制地合成某些性价比很高的装备。现在,英雄Spectre有M个金币,他想用这些钱购买装备使自己的力量值尽量高。你能帮帮他吗?他会教你魔法Haunt(幽灵附体)作为回报的。

Tag

动态规划

解决思路

这题麻烦的地方就在于,当一个物品被用来合成更高级的物品时,它原来的力量值不能算进去,而往高级合成,虽然我们知道它的合成上限,但不能保证基础物品的数量不超过限制,所以与常规的树型动态规划有些不同,在计算一个点的值时不能只考虑它和它的子树,还要考虑到它的父亲。
首先,由儿子转移过来的信息,可以得到每一个物品实际上需要多少钱,实际上最多能合成多少。然后设F[i][j][k]表示i这个物品,把j个i物品用于上面的合成,总共花费k元的最大力量值。当然首先还是递归处理出儿子的信息,然后返回来枚举这一次总共合成多少个i,然后再枚举从儿子出应该转移过来多少个,花多少钱,最后再枚举这生成的这么多个留多少个给自己,多少个传递给上一层。有些复杂。

代码

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;

#define ll long long
#define mem(Arr,x) memset(Arr,x,sizeof(Arr))

const int maxN=60;
const int maxM=maxN*maxN*4;
const int maxW=2010;
const int maxL=201;
const int inf=47483647;

class Edge
{
public:
    int v,cnt;
};

int n,m;
int edgecnt=0,Head[maxN],Next[maxM],Degree[maxN];
Edge E[maxM];
int Limit[maxN],Cost[maxN],W[maxN];
bool Leaf[maxN];
int F[maxN][maxL][maxW];
int G[maxN][maxW],H[maxN][maxW];

void Add_Edge(int u,int v,int cnt);
void dfs(int u);

int main()
{
    ios::sync_with_stdio(false);
    mem(Head,-1);mem(F,-0x3f3f3f3f);
    cin>>n>>m;
    for (int i=1;i<=n;i++)
    {
        char opt;cin>>W[i]>>opt;
        if (opt=='A')
        {
            int C;cin>>C;
            while (C--)
            {
                int v,cnt;cin>>v>>cnt;
                Add_Edge(i,v,cnt);
                Leaf[i]=0;
            }
        }
        if (opt=='B')
        {
            cin>>Cost[i]>>Limit[i];
            Limit[i]=min(Limit[i],m/Cost[i]);
            Leaf[i]=1;
        }
    }
    int tot=0;
    for (int node=1;node<=n;node++)
        if (Degree[node]==0)
        {
            dfs(node);
            tot++;
            for (int i=0;i<=m;i++)//枚举花多少钱
                for (int j=0;j<=i;j++)//枚举这i元钱中有多少从上一次转移过来
                    for (int k=0;k<=Limit[node];k++)//枚举这一次node号选择合成多少个
                        H[tot][i]=max(H[tot][i],H[tot-1][j]+F[node][k][i-j]);
        }
    int Ans=0;
    for (int i=0;i<=m;i++) Ans=max(Ans,H[tot][i]);
    cout<<Ans<<endl;
    return 0;
}

void Add_Edge(int u,int v,int cnt)
{
    edgecnt++;Next[edgecnt]=Head[u];Head[u]=edgecnt;E[edgecnt].v=v;E[edgecnt].cnt=cnt;
    Degree[v]++;
    return;
}

void dfs(int u)
{
    if (Leaf[u]==1)//叶子节点
    {
        for (int i=0;i<=Limit[u];i++)//枚向上贡献多少个
            for (int j=i;j<=Limit[u];j++)//枚举总共多少个,那么j-i就是自己保留的个数
                F[u][i][j*Cost[u]]=W[u]*(j-i);
        return;
    }
    Limit[u]=inf;
    for (int i=Head[u];i!=-1;i=Next[i])
    {
        dfs(E[i].v);
        Cost[u]+=Cost[E[i].v]*E[i].cnt;
        Limit[u]=min(Limit[u],Limit[E[i].v]/E[i].cnt);
    }
    Limit[u]=min(Limit[u],m/Cost[u]);
    mem(G,-0x3f3f3f3f);
    G[0][0]=0;//G[i][j]表示前i棵子树中,花费j元的最大力量值
    for (int l=Limit[u];l>=0;l--)//枚举合成多少个物品i
    {
        int tot=0;
        for (int e=Head[u];e!=-1;e=Next[e])
        {
            tot++;
            for (int i=0;i<=m;i++)//枚举这一次总共花多少钱
                for (int j=0;j<=i;j++)//枚举从这一棵子树转移过来多少钱,那么i-j就是从前面的子树转移过来的
                    G[tot][i]=max(G[tot][i],G[tot-1][i-j]+F[E[e].v][l*E[e].cnt][j]);
        }
        for (int i=0;i<=l;i++)//枚举这一次合成的l个物品i中,有多少个要用于上面的合成
            for (int j=0;j<=m;j++)
                F[u][i][j]=max(F[u][i][j],G[tot][j]+(l-i)*W[u]);
    }
    return;
}

本文章由SYCstudio或本站其它作者所有,严禁转载,转载必究

本文链接地址:[BZOJ1017/Luogu4037][JSOI2008]魔兽地图DotR(动态规划)


HNCJ OIer 一枚