OI技术宅

Tech Otakus save the world!
Welcome,my dear friends!
【I'm kiana/kiana810@126.com】

【JSOI2008】魔兽地图

【题目描述】

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

【输出】

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

【输入样例】

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

【输出样例】

33

【题解】

一开始看错题,以为是一张DAG,感觉好神啊不会做TAT

然后发现不大对劲,好像是一片森林,于是可以DP每棵树再背包合并?感觉随手TLE,好神啊还是不会做TAT

最后发现是棵树……

感觉还是不太会做,刚开始想的f[i][j]表示以i为根的子树花费j的最大收益,然而并想不到转移,把j换成数量,发现并不能完整表示状态……然而并没有想到合在一起……

设f[i][j][k]表示以i为根的子树中,合成j件i装备用于合成,总花费为k的最大能量,设g[i][j]表示某个节点前i棵子树花费为j时的最大收益,转移还是比较简单:

g[i][j]=max(g[i-1][j-k],f[son_u][num*need[son_u->u]][k]);

f[i][j][k]=max(g[tot][k]+(num-j)*v[i]);

含义脑补一下额……

最后取根节点状态的最大值即可。

【代码】

maya感觉再这么玩就滚粗了TAT

http://paste.ubuntu.com/11760107/

评论
热度(1)

© OI技术宅 | Powered by LOFTER