bzoj 1017 魔兽地图DotR

题目大意：

他们需要购买装备来提升自己的力量值，每件装备都可以使佩戴它的英雄的力量值提高固定的点数，所以英雄的力量值等于它购买的所有装备的力量值之和。装备分为基本装备和高级装备两种。基本装备可以直接从商店里面用金币购买，而高级装备需要用基本装备或者较低级的高级装备来合成，合成不需要附加的金币。装备的合成路线可以用一棵树来表示。比如，Sange and Yasha的合成需要Sange,Yasha和Sange and Yasha Recipe Scroll三样物品。其中Sange又要用Ogre Axe, Belt of Giant Strength和 Sange Recipe Scroll合成。每件基本装备都有数量限制，这限制了你不能无限制地合成某些性价比很高的装备。现在，英雄Spectre有M个金币，他想用这些钱购买装备使自己的力量值尽量高。

已知每个高级装备需要哪些初级下一级装备以及需要几个

思路：

树形dp

dp i j k表示第i种装备，有j个用于合成上一级装备，花k个金币

首先可以得到整个图应该是很多树

然后对于每个节点，我们都可以根据它的子树推出来

f[i][j][k]=max{c[i][k]+v[i]*(t-j)}

然后我们枚举这个节点有多少个需要用于合成（需要倒序枚举不然爆炸）

最后对于每棵树

我们可以枚举钱数，来求出这棵树买多少

 #include<iostream>

 #include<cstdio>

 #include<cmath>

 #include<algorithm>

 #include<cstring>

 #include<cstdlib>

 #include<queue>

 #include<vector>

 #include<set>

 #include<map>

 #include<stack>

 #define inf 2147483611

 #define ll long long

 #define MAXN 55

 using namespace std;

 inline int read()

 {

     int x=,f=;

     char ch=getchar();

     while(!isdigit(ch)) {if(ch=='-') f=-;ch=getchar();}

     while(isdigit(ch)) {x=x*+ch-'';ch=getchar();}

     return x*f;

 }

 int n,m,v[MAXN],cst[MAXN],lim[MAXN];

 int cnt,to[MAXN*MAXN*],val[MAXN*MAXN*],first[MAXN],next[*MAXN*MAXN],ind[MAXN];//邻接表

 int f[MAXN][MAXN*][MAXN*],c[MAXN][MAXN*],res[MAXN][MAXN*];

 //f为dp数组 c记录某节点前x个子树花j个金币所获得最大收益 res记录前k棵树花j个金币获得最大收益

 void add(int u,int v,int d) {next[++cnt]=first[u],first[u]=cnt,val[cnt]=d,to[cnt]=v,ind[v]++;}

 void dp(int x)

 {

     if(!first[x])

     {

         lim[x]=min(lim[x],m/cst[x]);

         for(int i=;i<=lim[x];i++)

             for(int j=i;j<=lim[x];j++)

                 f[x][i][j*cst[x]]=v[x]*(j-i);

         return ;

     }

     lim[x]=inf;

     for(int i=first[x];i;i=next[i])

     {

         dp(to[i]);

         lim[x]=min(lim[x],lim[to[i]]/val[i]);

         cst[x]+=val[i]*cst[to[i]];

     }

     lim[x]=min(lim[x],m/cst[x]);

     memset(c,-0x3f3f3f3f,sizeof(c));

     c[][]=;

     int cntt;

     for(int t=lim[x];t>=;t--)

     {

         cntt=;

         for(int i=first[x];i;i=next[i])

         {

             cntt++;

             for(int j=;j<=m;j++)

                 for(int k=;k<=j;k++)

                     c[cntt][j]=max(c[cntt][j],c[cntt-][j-k]+f[to[i]][t*val[i]][k]);

         }

         for(int i=;i<=t;i++)

             for(int j=;j<=m;j++)

                 f[x][i][j]=max(f[x][i][j],c[cntt][j]+(t-i)*v[x]);

     }

 }

 int main()

 {

     memset(f,-0x3f3f3f3f,sizeof(f));

     n=read(),m=read();

     char ch[];int x,b,a,ans=;

     for(int i=;i<=n;i++)

     {

         v[i]=read();

         scanf("%s",ch);

         if(ch[]=='A')

         {

             x=read();

             for(int j=;j<=x;j++) {a=read(),b=read();add(i,a,b);}

         }

         else cst[i]=read(),lim[i]=read();

     }

     cnt=;

     for(int g=;g<=n;g++)

     {

         if(!ind[g])

         {

             dp(g);

             cnt++;

             for(int i=;i<=m;i++)

                 for(int j=;j<=i;j++)

                     for(int k=;k<=lim[g];k++)

                         res[cnt][i]=max(res[cnt][i],res[cnt-][j]+f[g][k][i-j]);

         }

     }

     for(int i=;i<=m;i++) ans=max(ans,res[cnt][i]);

     printf("%d",ans);

 }

orz vfk大佬速度惊人，博客太长了懒得看

巴特西

bzoj 1017 魔兽地图DotR

最新文章

热门文章