文档章节

BZOJ1017: [JSOI2008]魔兽地图DotR

o
 osc_0sz5p35w
发布于 2018/03/10 17:47
字数 1327
阅读 14
收藏 0

行业解决方案、产品招募中!想赚钱就来传!>>>

#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;
}
o
粉丝 0
博文 500
码字总数 0
作品 0
私信 提问
加载中
请先登录后再评论。
简单CMS

主要修改: 1)增加文章模块,文章列表显示在首页和单品页中; 2)增加店铺模块,店铺显示在首页和瀑布流页中; 3)增加网站地图模块; 4)增加sitemap模块; 5)增加第三方淘宝登录功能; ...

简单CMS
2012/12/25
4.2K
0
RSS地理位置格式规范--GeoRSS

GeoRSS是一种可侦测、聚集、分享、并在地图上标志出RSS消息来源中地理位置的格式规范,可应用在地理相关及地图类软件中。把这种能侦测出资讯中的地理位置的解码器(encodings)建构在一般的模...

匿名
2013/05/23
478
0
地图应用开发(android)使用百度地图sdk详解+案例附源码

一、申请密钥 百度地图api 的key:http://lbsyun.baidu.com/apiconsole/key ----------输入sh1和包名即可生成key。 注意:关于安全码 ( 数字签名;包名 ) 的获取 1、eclipse下获取(这个最简单...

茗香墨语
2016/06/15
4.9K
0
FusionMaps教程:如何设整个地图为热点

JS地图工具FusionMaps教程:如何设整个地图为热点?用FusionMaps时我们还可以把整个地图设为一个热点。这绝对是个有用的功能。一般我们只展示一个地图的缩略图,但当你点击它的时候就能打开整...

mamahuhu
2014/05/15
29
0
FusionMaps应用实例在线Demo

FusionMaps XT让您使用JavaScript(HTML5)和Flash来展示与地理相关的数据,按类别、地区或实体进行分类。您可以用它有效地绘制各地区的收入数据、各省人口的普查信息、选举结果、飞行路线、...

mamahuhu
2014/05/16
24
0

没有更多内容

加载失败,请刷新页面

加载更多

数据获取的小技巧

在大数据如此火的时代,我们要获取更多数据,就要进行数据采集,过滤,然后再进行使用。比如当我们在进行一个项目并且需要大量真实数据时,就需要通过爬虫去获得,有些爬取额数据还不能直接使用,...

xiaotaomi7
25分钟前
21
0
docker cp 容器和虚拟机间的数据拷贝

容器复制到主机 docker cp {container_name}:{source_path} {target_path}#例子: docker cp php:www/php.ini /home/alex/php.ini 主机复制到容器 docker cp {source_path} {container_nam......

关元
34分钟前
25
0
spring boot整合kafaka批量消费

spring boot整合kafaka批量消费: 配置文件: kafka: producer: bootstrap-servers: 127.0.0.1:9092 batch-size: 16785 #一次最多发送数据量 retries: 1 #发送失败后的重复发送次数 buffer-m...

漫步行者
38分钟前
7
0
最新苹果多屏电脑控制技术---ios群控/苹果群控/一键实时同步操作/入门安装步骤以及功能讲解

创联苹果群控是一款通过无线发送命令来操作主控手机来带动全部被控手机,主控手机怎么操作被控手机全部同步进行相同操作,支持一键每台手机输入不一样的文字!无需连接USB数据线、无需XP框架...

osc_bodzcw38
39分钟前
10
0
NOIP模拟赛 编码

题目描述 一个字符串str的p型编码a的定义如下:把str表示成b1个c1,b2个c2…bn个cn,然后将b1,c1,b2,c2,…,bn,cn收尾拼接成的字符串中最短的字符串设为a。例如:字符串122344111可被描述为"1个...

osc_wcs4pa6z
40分钟前
17
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部