一行包含一个整数 $S$，表示最多可以提升多少点力量值。
| 题目名称 | 1855. [JSOI 2008]魔兽地图 |
|---|---|
| 输入输出 | bzoj_1017.in/out |
| 难度等级 | ★★★☆ |
| 时间限制 | 2000 ms (2 s) |
| 内存限制 | 162 MiB |
| 测试数据 | 10 |
| 题目来源 |
 Asm.Def
于2014-12-07加入 |
| 开放分组 | 全部用户 |
| 提交状态 | |
| 分类标签 | |
| 分享题解 |
| 通过：13， 提交：123， 通过率：10.57% | ||||
 神利·代目 |
100 | 0.402 s | 88.68 MiB | C++ |
 TA |
100 | 0.404 s | 88.68 MiB | C++ |
 丶 |
100 | 0.542 s | 47.55 MiB | C++ |
 Soviets |
100 | 0.562 s | 41.58 MiB | C++ |
|
TA |
100 | 0.595 s | 88.68 MiB | C++ |
 天一阁 |
100 | 1.162 s | 52.23 MiB | C++ |
|
天一阁 |
100 | 1.195 s | 52.23 MiB | C++ |
 soler |
100 | 1.219 s | 47.01 MiB | C++ |
 Asm.Def |
100 | 1.808 s | 82.94 MiB | C++ |
 thomount |
100 | 2.861 s | 44.58 MiB | C++ |
| 本题关联比赛 | |||
| 4043级2023省选练习赛6 | |||
| 关于 魔兽地图 的近10条评论(全部评论) | ||||
|---|---|---|---|---|
|
= =这道题数据也太弱了吧。。给一组强数据：
http://paste.ubuntu.com/10925780/ TA
2015-04-28 20:43
4楼
| ||||
|
这个题数据有点水啊 。。O(100*n*m)≈10^10都过了9个点（只有一组极限数据）。
TA
2015-04-27 21:01
3楼
| ||||
|
小心两个 0xaf0xaf0xaf0xaf 相加会溢出，变为正数
所以初始化时memset(f,0xacf,sizeof(f)) 多一份ac多一份保障  | ||||
|
写错了个初始化。。。调试了十多天
 。。。。。 | ||||
【题目描述】
$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$（幽灵附体）作为回报的。
【输入格式】
输入文件第一行包含两个整数 $N$ 和 $M$,分别表示装备的种类数和金币数。
装备用 $1$ 到 $N$ 的整数编号。
接下来的 $N$ 行，按照装备 $1$ 到装备 $N$ 的顺序，每行描述一种装备。
每一行的第一个正整数表示这个装备贡献的力量值。
接下来的非空字符表示这种装备是基本装备还是高级装备，$A$ 表示高级装备，$B$ 表示基本装备。
如果是基本装备，紧接着的两个正整数分别表示它的单价（单位为金币）和数量限制（不超过$100$）。
如果是高级装备，后面紧跟着一个正整数 $C$，表示这个高级装备需要 $C$ 种低级装备。后面的$2C$ 个数，依次描述某个低级装备的种类和需要的个数。
【输出格式】
【样例1输入】
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
【样例1输出】
33
【样例2】
点击下载样例2