[BZOJ1017/Luogu4037][JSOI2008]魔兽地图DotR(动态规划)

发布于 2018-04-08  192 次阅读


本文章由SYCstudio或本站其它作者所有,请勿擅自转载

本文链接地址:[BZOJ1017/Luogu4037][JSOI2008]魔兽地图DotR(动态规划)

Description

DotR (Defense of the Robots) Allstars是一个风靡全球的魔兽地图,他的规则简单与同样流行的地图DotA(Defense of the Ancients) Allstars。DotR里面的英雄只有一个属性——力量。他们需要购买装备来提升自己的力量值,每件装备都可以使佩戴它的英雄的力量值提高固定的点数,所以英雄的力量值等于它购买的所有装备的力量值之和。装备分为基本装备和高级装备两种。基本装备可以直接从商店里面用金币购买,而高级装备需要用基本装备或者较低级的高级装备来合成,合成不需要附加的金币。装备的合成路线可以用一棵树来表示。比如,Sangeand Yasha的合成需要Sange,Yasha和Sange and Yasha Recipe Scroll三样物品。其中Sange又要用Ogre Axe, Belt of Giant Strength和 Sange Recipe Scroll合成。每件基本装备都有数量限制,这限制了你不能无限制地合成某些性价比很高的装备。现在,英雄Spectre有M个金币,他想用这些钱购买装备使自己的力量值尽量高。你能帮帮他吗?他会教你魔法Haunt(幽灵附体)作为回报的。

Tag

动态规划

解决思路

这题麻烦的地方就在于,当一个物品被用来合成更高级的物品时,它原来的力量值不能算进去,而往高级合成,虽然我们知道它的合成上限,但不能保证基础物品的数量不超过限制,所以与常规的树型动态规划有些不同,在计算一个点的值时不能只考虑它和它的子树,还要考虑到它的父亲。
首先,由儿子转移过来的信息,可以得到每一个物品实际上需要多少钱,实际上最多能合成多少。然后设F[i][j][k]表示i这个物品,把j个i物品用于上面的合成,总共花费k元的最大力量值。当然首先还是递归处理出儿子的信息,然后返回来枚举这一次总共合成多少个i,然后再枚举从儿子出应该转移过来多少个,花多少钱,最后再枚举这生成的这么多个留多少个给自己,多少个传递给上一层。有些复杂。

代码

本文章由SYCstudio或本站其它作者所有,请勿擅自转载

本文链接地址:[BZOJ1017/Luogu4037][JSOI2008]魔兽地图DotR(动态规划)


HNCJ OIer