BZOJ1017: [JSOI2008]魔兽地图DotR

2018/03/10 17:47
阅读数 20

#1017: [JSOI2008]魔兽地图DotR Time Limit: 30 Sec Memory Limit: 162 MB Submit: 2781 Solved: 1095 [Submit][Status][Discuss] ##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 33 ##HINT

##Source

#题解 神题 父亲节点对孩子的选择有依赖,即孩子能给父亲提供多少夜叉/散华/食人魔之斧/巨人力量腰带/欢欣之刃精灵皮靴/夜叉卷轴/散华卷轴/.... 一个星期没打dota了T.T

$dp_1[x][j][k]$表示$x$这个物品,有$j$件用于上层合成,花费金钱$k$所能获得的最大价值 考虑做$l$件物品$x$ $dp_2[i][j]$表示前$i$棵子树,花费金钱$j所$能获得的最大价值 考虑前$i - 1$棵子树花费金钱$k$ $$dp_2[i][j] = max(dp_2[i - 1][k] + dp_1[son_i][l * num[x][son_i]][j - k])$$ 这样,$dp_1$转移为 $$dp_1[x][j][k] = max(dp_2[tot][k] + (l - j) * val[x]) $$ 最后这个题还有可能是个森林,需要泛化物品做一下。 手残写成完全背包了调了一天(呜呜呜……

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <map>
#include <cmath>
inline int max(int a, int b){return a > b ? a : b;}
inline int min(int a, int b){return a < b ? a : b;}
inline int abs(int x){return x < 0 ? -x : x;}
inline void swap(int &x, int &y){int tmp = x;x = y;y = tmp;}
inline void read(int &x)
{
    x = 0;char ch = getchar(), c = ch;
    while(ch < '0' || ch > '9') c = ch, ch = getchar();
    while(ch <= '9' && ch >= '0') x = x * 10 + ch - '0', ch = getchar();
    if(c == '-') x = -x;
}
const int INF = 0x3f3f3f3f;
int n, m, fa[60], val[60], c[60], lim[60], tpnum[60], tp[60][60], num[60][60], ans;
char s[10];
int dp1[60][110][2010], dp2[60][2010], dp3[2010];

void dfs(int x)
{
	if(!tpnum[x])
	{
		lim[x] = min(lim[x], m/c[x]);
		for(int l = 0;l <= lim[x];++ l)
			for(int j = 0;j <= l;++ j)
				dp1[x][j][l * c[x]] = val[x] * (l - j);
		return;
	}
	
	for(int i = 1;i <= tpnum[x];++ i)
	{
		int v = tp[x][i];
		dfs(v);
		c[x] += c[v] * num[x][i];
		lim[x] = min(lim[x], lim[v]/num[x][i]);
	}
	for(int l = 0;l <= lim[x];++ l)
	{
		memset(dp2, -0x3f, sizeof(dp2));
		dp2[0][0] = 0;
		for(int i = 1;i <= tpnum[x];++ i)
		{
			int v = tp[x][i];
			for(int j = 0;j <= m;++ j)
				for(int k = 0;k <= j;++ k)
					dp2[i][j] = max(dp2[i][j], dp2[i - 1][j - k] + dp1[v][l * num[x][i]][k]);
		}
		for(int j = 0;j <= l;++ j)
			for(int k = 0;k <= m;++ k)
				dp1[x][j][k] = max(dp1[x][j][k], dp2[tpnum[x]][k] + (l - j) * val[x]);
	}
}
int main()
{
	read(n), read(m);
	memset(lim, 0x3f, sizeof(lim));memset(dp1, -0x3f, sizeof(dp1));
	for(int i = 1;i <= n;++ i) 
	{
		read(val[i]);
		scanf("%s", s + 1);
		if(s[1] == 'A')
		{
			read(tpnum[i]);
			for(int j = 1;j <= tpnum[i];++ j)
				 read(tp[i][j]), fa[tp[i][j]] = i, read(num[i][j]);
		}
		else read(c[i]), read(lim[i]), lim[i] = min(lim[i], m/c[i]);
	}
	for(int i = 1;i <= n;++ i)
		if(!fa[i])
		{
			dfs(i);int tmp = 0;
			for(int j = m;j >= 0;-- j)
				for(int k = 0;k <= j;++ k)
						dp3[j] = max(dp3[j], dp3[j - k] + dp1[i][0][k]);
		}
	printf("%d", dp3[m]);
    return 0;
}
展开阅读全文
打赏
0
0 收藏
分享
加载中
更多评论
打赏
0 评论
0 收藏
0
分享
返回顶部
顶部