「APIO2014」序列分割「斜率优化」

· · 题解

首先，这题答案与切的顺序无关

证明很好证，考虑将一块abc分为a,b,c三块

方法一：先分成a,bc。答案为a (b + c) + bc = ab + ac + bc

方法二：先分成ab,c。答案为c (a + b) + ab = ab + ac + bc

答案相同。

然后考虑dp方程：若s[x]=\sum_{i=1}^x a[i]，令f[i][j]表示前i个数分j次的最大得分

f[i][j]=min_{0\leq l<i}(f[l][j - 1] + s[l] * (s[i] - s[l]))

需要滚动数组存，以下用f[i]表示f[i][j-1]（前驱状态）

然后考虑当i选j转移优于l时：（以下默认j < l）

f[j] + s[j]s[i] - s[j]^2 > f[l] + s[l]s[i] - s[l]^2 f[j] - s[j]^2 - (f[l] - s[l]^2) > (s[l]- s[j])s[i] \frac{f[j] - s[j]^2 - (f[l] - s[l]^2)}{- s[j] -(-s[l])} > s[i]

把每个点看做P_i(-s[i],f[i]-s[i]^2)，那么单调队列维护一个点集，斜率递增

这些点形成了一个在第三象限的下凸包

操作：

队头更新：若slope(q[head], q[head + 1]) \leq s[i]则出队（显然）

队尾更新：若slope(q[back - 1], q[back]) \geq slope(q[back], i)则出队

队尾操作的证明（也就是对凸包的证明）：

考虑q[back]可不可能做队头。若满足刚刚上方的条件，则：

若slope(q[back],q[back-1]) \leq s[i]使得q[back]成了队首

这时候当前的slope比刚刚的还要小，因此将继续出队，q[back]无法做队头。

斜率递增，故是一个凸包

还有一个细节：注意可能会出现a[i]=0，导致存在s[i] = s[j]，因此计算斜率应注意横坐标相同的情况，斜率为-\infty.

#include <algorithm>
#include <cstring>
#include <cstdio>
using namespace std;

typedef long long LL;

const int N = 1e5 + 10;

int n, k, fa[205][N];
LL s[N], f[N], g[N];

double slope(int a, int b) {
    LL x1 = - s[a], y1 = g[a] - s[a] * s[a];
    LL x2 = - s[b], y2 = g[b] - s[b] * s[b];
    if(x1 == x2) return -1e18;
    return (y2 - y1) / (double) (x2 - x1);
}

int main() {
    scanf("%d%d", &n, &k);
    for(int i = 1; i <= n; i ++) {
        scanf("%lld", s + i);
        s[i] += s[i - 1];
    }
    static int q[N], hd, bk;
    for(int t = 1; t <= k; t ++) {
        for(int i = 1; i <= n; i ++) g[i] = f[i]; 
        hd = bk = 0;
        for(int i = 1; i <= n; i ++) {
            for(; bk - hd >= 2 && slope(q[hd], q[hd + 1]) <= s[i]; hd ++) ;
            f[i] = 0;
            if(hd < bk) {
                int & j = q[hd]; fa[t][i] = j;
                f[i] = g[j] + s[j] * (s[i] - s[j]);
            }
            for(; bk - hd >= 2 && slope(q[bk - 1], q[bk - 2]) >= slope(i, q[bk - 1]); bk --) ;
            q[bk ++] = i;
        }
    }
    printf("%lld\n", f[n]);
    for(int x = fa[k][n]; k; x = fa[-- k][x])
        printf("%d ", x);
    return 0;
}

upd: 感谢@chennengkuan 指出定义的小错误