hdu 3339 In Action

<a target="_blank" href="http://acm.hdu.edu.cn/showproblem.php?pid=3339">点击打开链接hdu 3339</a>

思路：最短路+floyd+0/1背包

分析：

1 这一题多了一个限制条件能量，即每一点都有一个自己的能量值。

2 问题是要求能量至少要大于1/2的情况下的最短路，最开始我理解成是贪心，然后就是无休止的的WA，后来才知道是dp。其实很好理解，对于每一个点的能量只有两种选择取或者不取，那么这就是典型的0/1背包问题。但是有一个问题就是选取什么作为背包的容量，刚开始我选择pow_sum作为背包的容量，然后距离为价值求dp，然后又是一顿WA。后来改成了以cost_sum作为背包的容量，然后pow作为价值求解dp，最后判断是否有一个

dp[i] &gt; sum/2然后就1 A了。

3 注意题目明确指出有多个坦克，意思就是每一个坦克都从0开出并且只能攻击一个点。

代码：