BZOJ3675【APIO2014】序列分割 <斜率优化>

Problem

【APIO2014】序列分割

Description

最近迷上了一个分隔序列的游戏。
在这个游戏里，需要将一个长度为的非负整数序列分割成个非空的子序列。
为了得到个子序列，需要重复次以下的步骤：

首先选择一个长度超过的序列（一开始只有一个长度为的序列，也就是一开始得到的整个序列）
选择一个位置，并通过这个位置将这个序列分割成连续的两个非空的新序列

每次进行上述步骤之后，将会得到一定的分数。这个分数为两个新序列中元素和的乘积。
希望选择一种最佳的分割方式，使得轮之后，的总得分最大。

Input

输入第一行包含两个整数。
第二行包含个非负整数，表示一开始得到的序列。

Output

输出第一行包含一个整数，为可以得到的最大分数。

Sample Input

1 2	7 3 4 1 3 4 0 2 3

Sample Output

Hint

在样例中，可以通过如下3轮操作得到108分：

一开始有一个序列。选择在第个数之后的位置将序列分成两部分，并得到分。
这一轮开始时有两个序列：。选择在第3个数字之后的位置将第二个序列分成两部分，并得到分。
这一轮开始时有三个序列：。选择在第个数字之后的位置将第三个序列分成两部分，并得到分。

经过上述三轮操作，将会得到四个子序列：并总共得到分。

标签：斜率优化DP

Solution

易得方程：表示玩轮时只考虑区间内的数的最大贡献。那么有。
简单推一推：

套上斜率优化：

注意这里不要写成斜率的形式，因为可能等于。
按照不等式用单调栈对每层进行维护即可，这里可以做次一维，每次重新算数组。

Code

#include <bits/stdc++.h>
#define MAX_N 100000
using namespace std;
typedef long long lnt;
template <class T> inline void read(T &x) {
    x = 0; int c = getchar(), f = 1;
    for (; !isdigit(c); c = getchar()) if (c == 45) f = -1;
    for (; isdigit(c); c = getchar()) (x *= 10) += f*(c-'0');
}
int n, m, l, r, que[MAX_N+5]; lnt s[MAX_N+5];
lnt f[MAX_N+5], a[MAX_N+5], b[MAX_N+5];
bool chk(int p, int l, int r) {
    lnt x = (b[p]-b[que[r]])*(a[que[r-1]]-a[que[r]]);
    lnt y = (b[que[r]]-b[que[r-1]])*(a[que[r]]-a[p]);
    return x <= y;
}
int main() {
    read(n), read(m);
    for (int i = 1, x; i <= n; i++)
        read(x), s[i] = s[i-1]+x;
    for (int i = 1; i <= n; i++)
        a[i] = s[i], b[i] = -s[i]*s[i];
    for (int k = 1; k <= m; k++) {
        que[l = r = 0] = 0;
        for (int i = 1; i <= n; i++) {
            while (l < r && s[i]*(a[que[l]]-a[que[l+1]]) <= b[que[l+1]]-b[que[l]]) l++;
            f[i] = a[que[l]]*s[i]+b[que[l]]; while (l < r && chk(i, l, r)) r--; que[++r] = i;
        }
        for (int i = 1; i <= n; i++) b[i] = f[i]-s[i]*s[i];
    }
    return printf("%lld\n", f[n]), 0;
}