题目地址：洛谷：【P3648】[APIO2014]序列分割 – 洛谷、BZOJ：Problem 3675. — [Apio2014]序列分割

题目描述

你正在玩一个关于长度为n的非负整数序列的游戏。这个游戏中你需要把序列分成k+1个非空的块。为了得到k+1块，你需要重复下面的操作k次：
选择一个有超过一个元素的块（初始时你只有一块，即整个序列）
选择两个相邻元素把这个块从中间分开，得到两个非空的块。
每次操作后你将获得那两个新产生的块的元素和的乘积的分数。你想要最大化最后的总得分。

输入输出格式

输入格式：
第一行包含两个整数n和k。保证k+1≤n。
第二行包含n个非负整数a1,a2,⋯,an (0≤ai≤10^4)，表示前文所述的序列。

输出格式：
第一行输出你能获得的最大总得分。
第二行输出k个介于1到n−1之间的整数，表示为了使得总得分最大，你每次操作中分开两个块的位置。第i个整数si表示第i次操作将在si和si+1之间把块分开。
如果有多种方案使得总得分最大，输出任意一种方案即可。

输入输出样例

输入样例#1：

7 3
4 1 3 4 0 2 3

输出样例#1：

108
1 3 5

说明

限制与约定
第一个子任务共 11 分，满足 1≤k<n≤10。
第二个子任务共 11 分，满足 1≤k<n≤50。
第三个子任务共 11 分，满足 1≤k<n≤200。
第四个子任务共 17 分，满足 2≤n≤1000,1≤k≤min⁡{n−1,200}。
第五个子任务共 21 分，满足 2≤n≤10000,1≤k≤min⁡{n−1,200}。
第六个子任务共 29 分，满足 2≤n≤100000,1≤k≤min⁡{n−1,200}。

题解

首先我们来试一下把一段序列割成3段的两种割法：
假如有序列 a_1 \sim a_n ，我们割成 a_1 \sim a_i, a_{i+1} \sim a_j, a_{j+1} \sim a_n 三段，前缀和数组是s，先割i后割j的得分是 (s[n] - s[i]) * s[i] + (s[n] - s[j]) * (s[j] - s[i]) ，先割j后割i的得分是 (s[n] - s[j]) * s[j] + (s[j] - s[i]) * s[i] 。我们把它都展开，然后惊奇地发现，他们居然是相等的。
我们设计状态dp[i][j]表示前j个元素切了i刀的最大得分，有了上面的性质，转移就好办了：
dp[i][j] = \max_{k < j}\{ dp[i - 1][k] + s[k] * (s[j] - s[k]) \}
后面的得分怎么计算？我们可以认为是从后往前切，那么这一刀就是第一刀，计算方式就是上面写的那样。毕竟怎么切法得分都是一样的。
但是，现在的转移是O(n)的，总复杂度是O(n^2k)的，需要优化。
首先考虑把i维度用滚动数组优化掉空间，然后来推斜率优化。
现在有j、k两个位置，k>j，k优于j，令f[j] = dp[i - 1][j]，则要满足
f[k] + s[k] * (s[i] - s[k]) \geq f[j] + s[j] * (s[i] - s[j])
移项得
f[k] - f[j] - s[k]^2 + s[j]^2 \geq s[i] * (s[j] - s[k])
斜率式是
\frac{f[k] - f[j] - s[k]^2 + s[j]^2}{s[j] - s[k]} \geq s[i]
现在的复杂度是O(nk)的了，已经可以接受了。
但是！题目有个坑，ai可以是0，那这个位置切不切无所谓了，需要特判一下让它斜率极大/极小。
至于方案，记录下来如何转移的就可以了。

代码

注：代码中dp维度和上面题解的不一样。

// Code by KSkun, 2018/3
#include <cstdio>

typedef long long LL;

inline char fgc() {
    static char buf[100000], *p1 = buf, *p2 = buf;
    return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2) ? EOF : *p1++;
}

inline int readint() {
    register int res = 0, neg = 1;
    char c = fgc();
    while(c < '0' || c > '9') {
        if(c == '-') neg = -1;
        c = fgc();
    }
    while(c >= '0' && c <= '9') {
        res = res * 10 + c - '0';
        c = fgc();
    }
    return res * neg;
}

const int MAXN = 100005, MAXK = 205;

int n, k, pre[MAXK][MAXN], l, r, q[MAXN];
bool type = false;
LL s[MAXN], dp[MAXN][2];

inline LL sqr(LL x) {
    return x * x;
}

inline double slope(int j, int k) {
    if(s[j] == s[k]) return -1e18;
    return double(dp[k][type ^ 1] - dp[j][type ^ 1] - sqr(s[k]) + sqr(s[j])) / (s[j] - s[k]);
}

int main() {
    n = readint();
    k = readint();
    for(int i = 1; i <= n; i++) {
        s[i] = s[i - 1] + readint();
    }
    for(int p = 1; p <= k; p++) {
        l = r = 0;
        type ^= 1;
        for(int i = 1; i <= n; i++) {
            while(l < r && slope(q[l], q[l + 1]) <= s[i]) l++;
            dp[i][type] = dp[q[l]][type ^ 1] + s[q[l]] * (s[i] - s[q[l]]);
            pre[p][i] = q[l];
            while(l < r && slope(q[r], i) <= slope(q[r - 1], q[r])) r--;
            q[++r] = i;
        }
    }
    printf("%lld\n", dp[n][type]);
    for(int p = k, u = n; p >= 1; p--) {
        u = pre[p][u];
        printf("%d ", u);
    }
    return 0;
}