tkdsheep-solution-0109

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

{{{
植物大战绵羊@.@

给m*n个格子，有些格子可以造植物，绵羊有一个出生点，一个目标点，绵羊会选最短且字典序最小的路径走向目标点，因此绵羊的路径是固定的，即每个格子是否会有绵羊经过都是知道的

因为植物是范围攻击，不管来多少只绵羊，每只绵羊受到同等的伤害，所以绵羊出现的时间是多余的条件，并且只要血最多的绵羊能被打死就ok

所以问题就很简单了，把所有可以造植物的格子提取出来，然后就变成一个背包问题，如果将总能量V分配到这些格子上，使得总的伤害最大

不过这个数组范围很难估计，格子最多可能有900个左右，如果全部可以造植物的话，最大能量需求会达到900*100*5（植物最多升5级），但实际达不到这么多，我AC的程序用的是滚动数组dp[2][1000000]

另外注意不能dp的时候才去判断植物能打哪些格子，应该预处理出来

还有就是求最短路径的时候，要从终点倒过来向起点求，因为是字典序最小

}}}

{{{
如果注意到羊的 hp 上限是 1024 的话，做背包时可以用羊的血量作为数组下标，最小化能量需求，这样就不需要开那么大的数组了

By 猛犸也钻地
}}}


{{{
萌学长dbl。。没想到这个，一开始就先入为主要造成最大的伤害@.@ by大肥羊
}}}

植物大战绵羊@.@
给m*n个格子，有些格子可以造植物，绵羊有一个出生点，一个目标点，绵羊会选最短且字典序最小的路径走向目标点，因此绵羊的路径是固定的，即每个格子是否会有绵羊经过都是知道的
因为植物是范围攻击，不管来多少只绵羊，每只绵羊受到同等的伤害，所以绵羊出现的时间是多余的条件，并且只要血最多的绵羊能被打死就ok
所以问题就很简单了，把所有可以造植物的格子提取出来，然后就变成一个背包问题，如果将总能量V分配到这些格子上，使得总的伤害最大
不过这个数组范围很难估计，格子最多可能有900个左右，如果全部可以造植物的话，最大能量需求会达到900*100*5（植物最多升5级），但实际达不到这么多，我AC的程序用的是滚动数组dp[2][1000000]
另外注意不能dp的时候才去判断植物能打哪些格子，应该预处理出来
还有就是求最短路径的时候，要从终点倒过来向起点求，因为是字典序最小

如果注意到羊的 hp 上限是 1024 的话，做背包时可以用羊的血量作为数组下标，最小化能量需求，这样就不需要开那么大的数组了
By 猛犸也钻地

萌学长dbl。。没想到这个，一开始就先入为主要造成最大的伤害@.@ by大肥羊