HBC17622[NOI2009]植物大战僵尸题解

挑战自我，勇攀编程高峰！全网最全C++题库，助您成为编程达人。

Plants vs. Zombies（PVZ）是最近十分风靡的一款小游戏，Plants Plants Plants（植物）和Zombies Zombies Zombies（僵尸）是游戏的主角，其中Plants Plants Plants防守，而Zombies Zombies Zombies进攻，该款游戏包含多种不同的挑战系列，比如Protect Your Brain、Bowling等等，其中最

Plants vs. Zombies（PVZ）是最近十分风靡的一款小游戏。 Plants Plants Plants （植物）和 Zombies Zombies Zombies （僵尸）是游戏的主角，其中 Plants Plants Plants 防守，而 Zombies Zombies Zombies 进攻。该款游戏包含多种不同的挑战系列，比如Protect Your Brain、Bowling等等。其中最为经典的，莫过于玩家通过控制 Plants Plants Plants 来防守 Zombies Zombies Zombies 的进攻，或者相反地由玩家通过控制 Zombies Zombies Zombies 对 Plants Plants Plants 发起进攻。 现在，我们将要考虑的问题是游戏中 Zombies Zombies Zombies 对 Plants Plants Plants 的进攻，请注意，本题中规则与实际游戏有所不同。游戏中有两种角色， Plants Plants Plants 和 Zombies Zombies Zombies ，每个 Plant Plant Plant 有一个攻击位置集合，它可以对这些位置进行保护；而 Zombie Zombie Zombie 进攻植物的方式是走到植物所在的位置上并将其吃掉。 游戏的地图可以抽象为一个 N NN 行MMM列的矩阵，行从上到下用 0 0 0 到 N–1 N–1 N–1 编号，列从左到右用 0 0 0 到 M–1 M–1 M–1 编号；在地图的每个位置上都放有一个 Plant Plant Plant ，为简单起见，我们把位于第r行第c列的植物记为 Pr,c P_{r,c} Pr,c​ 。  Plants Plants Plants 分很多种，有攻击类、防守类和经济类等等。为了简单的描述每个 Plant Plant Plant ，定义 Score Score Score 和 Attack Attack Attack 如下： Score[Pr,c]Score[P_{r,c}]Score[Pr,c​]:Zombie Zombie Zombie 击溃植物 Pr,c P_{r,c} Pr,c​ 可获得的能源。若 Score[Pr,c] Score[P_{r,c}] Score[Pr,c​] 为非负整数，则表示击溃植物 Pr,c P_{r,c} Pr,c​ 可获得能源 Score[Pr,c] Score[P_{r,c}] Score[Pr,c​] ，若为负数表示击溃 Pr,c P_{r,c} Pr,c​ 需要付出能源- Score[Pr,c] Score[P_{r,c}] Score[Pr,c​] 。 Attack[Pr,c] Attack[P_{r,c}] Attack[Pr,c​]:植物 Pr,c P_{r,c} Pr,c​ 能够对 Zombie Zombie Zombie 进行攻击的位置集合。 Zombies Zombies Zombies 必须从地图的右侧进入，且只能沿着水平方向进行移动。 Zombies Zombies Zombies 攻击植物的唯一方式就是走到该植物所在的位置并将植物吃掉。因此 Zombies Zombies Zombies 的进攻总是从地图的右侧开始。也就是说，对于第 r r r 行的进攻， Zombies Zombies Zombies 必须首先攻击 Pr,M−1 P_{r,M-1} Pr,M−1​ ；若需要对 Pr,c（0≤c

标签： HBC17622[NOI2009]植物大战僵尸题解