BZOJ 3675 「APIO2014」序列分割

首先易证分割的顺序对答案没有影响（(a+b)c+ab=a(b+c)+bc）。
然后设 Fi,k 表示前 i 个数分割了 k 次的得分。
有转移 Fi,k=max0≤j<i(Fj,k−1+sumj(sumi−sumj))，其中 sumi=i∑j=1ai。

把第二维滚动，设 fi=Fi,k,gi=Fi,k−1，式子变为 fi=max0≤j<i(gj+sumj(sumi−sumj))。

对于 0≤k<j<i，设 j 优于 k，有 gj+sumj(sumi−sumj)≥gk+sumk(sumi−sumk)gj+sumjsumi−sum2j≥gk+sumksumi−sum2k(gj−sum2j)−(gk−sum2k)≥(sumk−sumj)sumi(gj−sum2j)−(gk−sum2k)sumk−sumj≤sumi

注意特判 sumj=sumk 的情况，这时斜率为 −∞。
维护一只下凸包即可。
输出方案的话，中途记录一下选择的决策。
然鹅 BZOJ 不需要输出方案……

代码：

#include <cstdio>
using namespace std;
const int N = 1e5;
const int K = 200;
int n,k;
int a[N + 5],pre[N + 5][K + 5];
int q[N + 5],head,tail;
long long sum[N + 5],f[N + 5],g[N + 5];
inline double slope(int x,int y)
{
    if(sum[x] == sum[y])
        return -0x3f3f3f3f3f3f3f3f;
    return (double)(g[x] - sum[x] * sum[x] - g[y] + sum[y] * sum[y]) / (sum[y] - sum[x]);
}
int main()
{
    scanf("%d%d",&n,&k);
    for(register int i = 1;i <= n;++i)
        scanf("%d",a + i),sum[i] = sum[i - 1] + a[i];
    for(register int i = 1;i <= k;++i)
    {
        q[head = tail = 1] = 0;
        for(register int j = 1;j <= n;++j)
        {
            for(;head < tail && slope(q[head],q[head + 1]) <= sum[j];++head);
            f[j] = g[q[head]] + sum[q[head]] * (sum[j] - sum[q[head]]),pre[j][i] = q[head];
            for(;head < tail && slope(q[tail - 1],q[tail]) >= slope(q[tail],j);--tail);
            q[++tail] = j;
        }
        for(register int j = 1;j <= n;++j)
            g[j] = f[j];
    }
    printf("%lld\n",f[n]);
    /*
    for(register int i = n,j = k;j;--j)
        printf("%d ",i = pre[i][j]);
    此处为输出方案，由于 BZOJ 没有 SPJ 所以省去该步骤。
    */
}