好长的DP程序！！！！！！

Accepted 有效得分：100 有效耗时：172ms

floyd+DP+模拟=AC~~

（虽然有点慢.....）

楼下有误！

对于同一个枪兵的位置，相同的HP，狗的位置并不是唯一的。

N楼下给出一个很好的反例：

00000

11111

00011

z101Z

00M00

14 8

比较猥琐的方法是加一维：一只狗的位置。

比较好的方法是用hash表。

预处理出点对点的最短路径的方向

用BFS

判重时只要记录 枪兵的位置 枪兵HP 两只狗的HP

因为狗的位置是由人的位置决定，所以无需记录

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

简单要死

這個小狗偷盜雷獸巢科技升了5級甲麽 = =

记忆化搜索过了

这题范围小所以数组可以尽量开

打到手酸

题主提示看到这道题，我们就会想到贪心。贪心有两种A. 根本不移动，原地攻击，不成功，便成仁反例：000000111z00ZM0111100000011 5原地不动会被包夹致死。正解请自己研究。B. 分为移动和攻击两个阶段。移动阶段只移动，攻击阶段只原地攻击。这个算法是对贪心A打了一个小补丁。刚才的反例固然解决了，能否保证最优呢？反例：000001111100011z101Z00M0014 8如果第一步向左或右移动一格，就白白被逼近一格。如果不移动，就会被包夹致死。正解请自己研究。贪心就被否决了，又难以建立好的图论模型。只能采取搜索和动态规划了。题主通过的程序就是使用动态规划。一个小小小小小小优化：大家会发现zergling HP 99大得有点突尤。其实，当2*zergling HP大于回合数时，任务必然失败。

解题方案谁有

看星星的好地方---|-屋顶

好不容易

先弄个天花板