题解：SP33372 LARMY - Lannister Army

· · 题解

这是一篇补充决策单调性的证明。

贡献的递推式就不加以说明了，题解都写的非常棒。

$dp_{i, j} = dp_{k, j - 1} + w(k + 1, i)

通过决策的单调性我们进行优化，可以写出下面的代码。

```cpp rep(k, 2, m) { //分割段数 rep_(i, n, k) { //右端点 rep(j, s[i][k - 1], s[i + 1][k]) { //左端点 if(dp[j][k - 1] + w[j + 1][i] < dp[i][k]) { dp[i][k] = dp[j][k - 1] + w[j + 1][i]; s[i][k] = j; } } } } ``` 那么，我们要证明 $s_{i, k - 1} \leq s_{i, k} \leq s_{i + 1, k}$，来说明代码的合理性。 - $s_{i, k - 1} \leq s_{i, k}

这个是显然的，数字选的一样时，后面的刀比前面的刀位置靠后。

先不看多出来的这第 i + 1 个数字，只考虑前 i 个数字。

由于 s_{i, k} 是为只取前 i 个数字时最优解，所以如果这一刀往前移了，只对于前 i 个数字的贡献，一定会更劣。

那么是否可以从第 i + 1 个数字的贡献找补呢？答案是否定的。

因为我们要最小化逆序对的数量。现在刀往前移，能和 i + 1 产生逆序对的数字数量一定不降。

因此 s_{i, k} \leq s_{i + 1, k} 得证。