「BZOJ1017」[JSOI2008] 魔兽地图DotR

2014年11月23日6,9704

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（幽灵附体）作为回报的。

Input

输入文件第一行包含两个整数，N (1 <= n <= 51) 和 m (0 <= m <= 2,000)。分别表示装备的种类数和金币数。装备用1到N的整数编号。接下来的N行，按照装备1到装备n的顺序，每行描述一种装备。每一行的第一个正整数表示这个装备贡献的力量值。接下来的非空字符表示这种装备是基本装备还是高级装备，A表示高级装备，B表示基本装备。如果是基本装备，紧接着的两个正整数分别表示它的单价（单位为金币）和数量限制（不超过100）。如果是高级装备，后面紧跟着一个正整数C，表示这个高级装备需要C种低级装备。后面的2C个数，依次描述某个低级装备的种类和需要的个数。

Output

第一行包含一个整数S，表示最多可以提升多少点力量值。

Sample Input

10 59
5 A 3 6 1 9 2 10 1
1 B 5 3
1 B 4 3
1 B 2 3
8 A 3 2 1 3 1 7 1
1 B 5 3
5 B 3 3
15 A 3 1 1 5 1 4 1
1 B 3 5
1 B 4 3

Sample Output

题解

好像就是个树形dp吧

为什么感觉好坑。。。

设P[x]，L[x]，M[x]，表示物品x的能量，购买上限与价格

L[x]=min（L[x]，m/M[x]）

高级装备的M和L随便dp一下

再用f[i][j][k]表示第i个物品，有j件用于上层的合成，花费金钱是k所能获得的最大力量

对于以x为根的子树，枚举合成 l 个 x 物品，然后再用其余的钱买一些 x 子树内的装备不用于合成

枚举合成物品数量 l ，用g[i][j]表示x的前i个儿子的子树，花费j的钱，所能获得的最大力量

g[tot][j]=max{g[tot-1][j-k]+f[e[i].to][l*e[i].v][k]}

//e[i].to是儿子结点，e[i].v是所需数量，就是从j中拿出k的钱在e[i].to的子树内购买

最后再枚举合成的 l 个 x 物品中有 j 个是直接用于增加力量，剩余用于合成的

f[x][j][k]=max{g[tot][k]+P[x]*(l-j)}

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<algorithm>
#define ll long long
#define inf 1000000000
using namespace std;
int read()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
int n,m,cnt,tot,ans;
int P[55],L[55],M[55];
int f[55][105][2005];
int g[55][2005],h[55][2005];
char ch[5];
int last[55],deg[55];
struct data{int to,next,v;}e[20005];
void insert(int u,int v,int w)
{
    e[++cnt].to=v;e[cnt].next=last[u];last[u]=cnt;e[cnt].v=w;
    deg[v]++;
}
void dp(int x)
{
    if(!last[x])
    {
        L[x]=min(L[x],m/M[x]);
        for(int i=0;i<=L[x];i++)
            for(int j=i;j<=L[x];j++)
                f[x][i][j*M[x]]=(j-i)*P[x];
        return;
    }
    L[x]=inf;
    for(int i=last[x];i;i=e[i].next)
    {
        dp(e[i].to);
        L[x]=min(L[x],L[e[i].to]/e[i].v);
        M[x]+=e[i].v*M[e[i].to];
    }
    L[x]=min(L[x],m/M[x]);
    memset(g,-0x3f3f3f3f,sizeof(g));
    g[0][0]=0;
    for(int l=L[x];l>=0;l--)
    {
        int tot=0;
        for(int i=last[x];i;i=e[i].next)
        {
            tot++;
            for(int j=0;j<=m;j++)
                for(int k=0;k<=j;k++)
                    g[tot][j]=max(g[tot][j],g[tot-1][j-k]+f[e[i].to][l*e[i].v][k]);
        }
        for(int j=0;j<=l;j++)
            for(int k=0;k<=m;k++)
                f[x][j][k]=max(f[x][j][k],g[tot][k]+P[x]*(l-j));
    }
}
int main()
{
    memset(f,-0x3f3f3f3f,sizeof(f));
    n=read();m=read();
    for(int i=1;i<=n;i++)
    {
        P[i]=read();
        scanf("%s",ch);
        if(ch[0]=='A')
        {
            int x=read();
            while(x--)
            {
                int v=read(),num=read();
                insert(i,v,num);
            }
        }
        else M[i]=read(),L[i]=read();
    }    
    for(int x=1;x<=n;x++)
		if(!deg[x])
        {
			dp(x);
			tot++;
			for(int i=0;i<=m;i++)
				for(int j=0;j<=i;j++)
					for(int k=0;k<=L[x];k++)
						h[tot][i]=max(h[tot][i],h[tot-1][j]+f[x][k][i-j]);
		}
	for(int i=0;i<=m;i++)
        ans=max(ans,h[tot][i]);
    printf("%d\n",ans);
    return 0;
}

#include<iostream>

#include<cstdio>

#include<cstring>

#include<cmath>

#include<cstdlib>

#include<algorithm>

#define ll long long

#define inf 1000000000

using namespace std;

int read()

{

int x=0,f=1;char ch=getchar();

while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}

while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}

return x*f;

}

int n,m,cnt,tot,ans;

int P[55],L[55],M[55];

int f[55][105][2005];

int g[55][2005],h[55][2005];

char ch[5];

int last[55],deg[55];

struct data{int to,next,v;}e[20005];

void insert(int u,int v,int w)

{

e[++cnt].to=v;e[cnt].next=last[u];last[u]=cnt;e[cnt].v=w;

deg[v]++;

}

void dp(int x)

{

if(!last[x])

{

L[x]=min(L[x],m/M[x]);

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

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

f[x][i][j*M[x]]=(j-i)*P[x];

return;

}

L[x]=inf;

for(int i=last[x];i;i=e[i].next)

{

dp(e[i].to);

L[x]=min(L[x],L[e[i].to]/e[i].v);

M[x]+=e[i].v*M[e[i].to];

}

L[x]=min(L[x],m/M[x]);

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

g[0][0]=0;

for(int l=L[x];l>=0;l--)

{

int tot=0;

for(int i=last[x];i;i=e[i].next)

{

tot++;

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

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

g[tot][j]=max(g[tot][j],g[tot-1][j-k]+f[e[i].to][l*e[i].v][k]);

}

for(int j=0;j<=l;j++)

for(int k=0;k<=m;k++)

f[x][j][k]=max(f[x][j][k],g[tot][k]+P[x]*(l-j));

}

int main()

{

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

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

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

{

P[i]=read();

scanf("%s",ch);

if(ch[0]=='A')

{

int x=read();

while(x--)

{

int v=read(),num=read();

insert(i,v,num);

}

else M[i]=read(),L[i]=read();

}

for(int x=1;x<=n;x++)

if(!deg[x])

{

dp(x);

tot++;

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

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

for(int k=0;k<=L[x];k++)

h[tot][i]=max(h[tot][i],h[tot-1][j]+f[x][k][i-j]);

}

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

ans=max(ans,h[tot][i]);

printf("%d\n",ans);

return 0;

}

« NOIP2014联合权值「BZOJ1060」[ZJOI2007] 时态同步 »

VANE

黄学长，在主函数里用f数组更新h数组的时候不需要枚举k的吧？直接从f[x][0][i-j]转移就好了，因为他是树根的吧？

请问这个时间复杂度不是O(100*n*m*m)么？

XXXYYY

我现在狂在TLE，受不了啊
思路跟这差不多
怎么办？？？？？

XXXYYY

时间复杂度很高啊
不会TLE吗

hzwer.com _ Home | http://hzwer.com

「BZOJ1017」[JSOI2008] 魔兽地图DotR

Description

Input

Output

Sample Input

Sample Output

题解

分类目录

热门文章

Myfriends

近期评论