题解 P3648 【[APIO2014]序列分割】

2019-01-07 08:00:58


容易发现分割的顺序对答案没有影响。

先写一个 $O(n^2k)$ 的暴力DP。

设 $f[i][j]$ 表示前 $j$ 个数切 $i$ 次的最大得分, $sum$ 是 $a$ 的前缀和,那么有

$$\large f[i][j]=\max\limits_{k=1}^{j-1}\big[f[i-1][k]+sum[k]\times(sum[j]-sum[k])\big]$$

假设 $k$ 比 $l$ 优,那么有

$$\large f[i-1][k]+sum[k]\times sum[j]-sum[k]^2>f[i-1][l]+sum[l]\times sum[j]-sum[l]^2$$

$$\large sum[k]\times sum[j]-sum[l]\times sum[j]>f[i-1][l]-f[i-1][k]-sum[l]^2+sum[k]^2$$

$$\large(sum[k]-sum[l])\times sum[j]>sum[k]^2-sum[l]^2-f[i-1][k]+f[i-1][l]$$

$$\large\frac{sum[k]^2-sum[l]^2-f[i-1][k]+f[i-1][l]}{sum[k]-sum[l]}<sum[j]$$

这些东西都是单调的,然后就可以做到 $O(nk)$ 了。

如果式子推错了请私信我qwq

代码见blog