Description

DotR (Defense of the Robots) Allstars是一个风靡全球的魔兽地图，他的规则简单与同样流行的地图DotA

(Defense of the Ancients) Allstars。DotR里面的英雄只有一个属性——力量。他们需要购买装备来提升自己的

力量值，每件装备都可以使佩戴它的英雄的力量值提高固定的点数，所以英雄的力量值等于它购买的所有装备的力

量值之和。装备分为基本装备和高级装备两种。基本装备可以直接从商店里面用金币购买，而高级装备需要用基本

装备或者较低级的高级装备来合成，合成不需要附加的金币。装备的合成路线可以用一棵树来表示。比如，Sange

and Yasha的合成需要Sange,Yasha和Sange and Yasha Recipe Scroll三样物品。其中Sange又要用Ogre Axe, Belt

 of Giant Strength和 Sange Recipe Scroll合成。每件基本装备都有数量限制，这限制了你不能无限制地合成某

些性价比很高的装备。现在，英雄Spectre有M个金币，他想用这些钱购买装备使自己的力量值尽量高。你能帮帮他

吗？他会教你魔法Haunt（幽灵附体）作为回报的。

Solution

父节点依赖子节点的奇怪的树形Dp

看黄学长的代码写的，一开始还写挂了，然后改呀改呀整个人有点凌乱

tips都在注释里了，不过写这道题还是推荐不要看我的题解

（vfk那个版本应该会快很多，但现在还没看懂QvQ）

#include
     
      #include
      
       #include
       
        #include
        
         #define Max(a,b) (a>b?a:b)#define Min(a,b) (a
         
          '9'){        if(c=='-')f=-1;c=getchar();    }    while(c>='0'&&c<='9'){        x=x*10+c-'0';c=getchar();    }    return x*f;}void work(int x){    if(vis[x])return;    vis[x]=1;    if(head[x]==-1)//如果是叶子结点     {        limit[x]=Min(limit[x],m/cost[x]);        for(int j=0;j<=limit[x];j++)//f[编号][用于上层的个数][钱]         for(int i=j;i<=limit[x];i++)//第x个物品合成i个，其中j个用于上层        {            f[x][j][i*cost[x]]=(i-j)*power[x];         }        return;    }    limit[x]=INF;    for(int i=head[x];~i;i=Edges[i].next)    {        int v=Edges[i].to;        work(v);        limit[x]=Min(limit[x],limit[v]/Edges[i].w);         cost[x]+=Edges[i].w*cost[v];    }    limit[x]=Min(limit[x],m/cost[x]);    memset(g,-INF,sizeof(g));    g[0][0]=0;    for(int l=limit[x];l>=0;l--)//枚举合成l个物品     {        int tot=0;        for(int i=head[x];~i;i=Edges[i].next)        {            tot++;            int v=Edges[i].to;            for(int j=0;j<=m;j++)//g[tot][j]:前tot个子树花费为j时获得的最大能量             for(int k=0;k<=j;k++)//在子树v上花费k时             g[tot][j]=Max(g[tot][j],g[tot-1][j-k]+f[v][l*Edges[i].w][k]);        }        for(int j=0;j<=l;j++)//l个物品中j个用于上层         for(int k=0;k<=m;k++)//花费k         f[x][j][k]=Max(f[x][j][k],g[tot][k]+power[x]*(l-j));    }}int main(){    memset(head,-1,sizeof(head));    memset(f,-INF,sizeof(f));//注意不能赋值为0，有好多状态其实无法达到     n=Read();m=Read();    for(int i=1;i<=n;i++)    {        power[i]=Read();        int son;        char c=getchar();        while(c!='A'&&c!='B')c=getchar();        if(c=='A')        {            son=Read();            for(int j=1;j<=son;j++)            {                int v,w;                v=Read();w=Read();                addedge(i,v,w);                deg[v]++;            }        }        else         {             cost[i]=Read();            limit[i]=Read();        }    }    for(int x=1;x<=n;x++)    {        if(!deg[x])        {            work(x);            num++;            for(int i=0;i<=m;i++)            for(int j=0;j<=i;j++)            for(int k=0;k<=limit[x];k++)//h[num][i]:前num棵树花费为i            {                h[num][i]=Max(h[num][i],h[num-1][j]+f[x][k][i-j]);                ans=Max(ans,h[num][i]);            }        }    }    printf("%d\n",ans);    return 0;}