题解：SP33372 LARMY - Lannister Army

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

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

dp_{i, j}

代表前

i

个数字，分割了

j

组时的最小不快乐值之和。那么可以写出如下的式子。

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

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

s_{i, j}

的含义时前

i

个数字，第

j - 1

刀砍的位置，也就是分出第

j

段的那一刀的位置。

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}$

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

$s_{i, k} \leq s_{i + 1, k}$

先不看多出来的这第

i + 1

个数字，只考虑前

i

个数字。

由于

s_{i, k}

是为只取前

i

个数字时最优解，所以如果这一刀往前移了，只对于前

i

个数字的贡献，一定会更劣。

那么是否可以从第

i + 1

个数字的贡献找补呢？答案是否定的。

因为我们要最小化逆序对的数量。现在刀往前移，能和

i + 1

产生逆序对的数字数量一定不降。

因此

s_{i, k} \leq s_{i + 1, k}

得证。

题解：SP33372 LARMY - Lannister Army

文章操作

相关推荐

评论

题解：SP33372 LARMY - Lannister Army