「BZOJ3675」[APIO2014]序列分割

Description

小H最近迷上了一个分隔序列的游戏。在这个游戏里,小H需要将一个长度为nn的非负整数序列分割成k+1k+1个非空的子序列。为了得到k+1k+1个子序列,小H需要重复kk次以下的步骤:

  1. 小H首先选择一个长度超过11的序列(一开始小H只有一个长度为nn的序列——也就是一开始得到的整个序列);
  2. 选择一个位置,并通过这个位置将这个序列分割成连续的两个非空的新序列。
    每次进行上述步骤之后,小H将会得到一定的分数。这个分数为两个新序列中元素和的乘积。小H希望选择一种最佳的分割方式,使得kk轮之后,小H的总得分最大。

Input

输入第一行包含两个整数nnk(k+1n)k(k+1\leq n)

第二行包含nn个非负整数a1,a2,,an(0ai104)a_1,a_2,\cdots ,a_n(0\leq a_i\leq 10^4),表示一开始小H得到的序列。

Output

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

Sample Input

1
2
7 3 
4 1 3 4 0 2 3

Sample Output

1
108

HINT

数据满足2n100000,1kmin(n1,200)2\leq n\leq 100000,1\leq k\leq \min(n -1,200)

Solution

x(y+z)+xy=(x+y)z+yzx(y+z)+xy=(x+y)z+yz
说明切割顺序不影响结果。

fi,jf_{i,j}表示前jj的元素切成ii块的最大价值。
fi,j=max{fi1,k+(sisk)sk}k[0,i1]f_{i,j}=\max\{f_{i-1,k}+(s_i-s_k)\cdot s_k\} k\in[0,i-1]
里面可以斜率优化嘛。去掉maxmax函数。第一维为了方便略去。
可以得到fk+sisksk2=fjsiskfj=sk2fkf_k+s_is_k-s_k^2=f_j\Rightarrow s_is_k-f_j=s_k^2-f_k
对每一个(sk,sk2fk)(s_k,s_k^2-f_k)维护下凸包。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<map>
#include<bitset>
#define mk make_pair
#define fi first
#define nd second
#define pii pair<int,int>
#define pb push_back
#define sqr(x) ((x)*(x))
using namespace std;
typedef long long ll;
inline ll read() {ll x = 0; char ch = getchar(), w = 1;while(ch < '0' || ch > '9') {if(ch == '-') w = -1;
ch = getchar();}while(ch >= '0' && ch <= '9') {x = x * 10 + ch - '0';ch = getchar();}return x * w;}
void write(ll x) {if(x < 0) putchar('-'), x = -x;if(x > 9) write(x / 10);putchar(x % 10 + '0');}
inline void writeln(ll x) {write(x);puts("");}
const int N = 210000;

int n, m;
ll s[N], a[N];
double slope(int x, int y, ll *f) {
if(s[x] == s[y]) return 1e18;
return (s[y] * s[y] - f[y] - (s[x] * s[x] - f[x])) / (double)(s[y] - s[x]);
}
ll f[2][N];
int q[N], head, tail;
int ans[N], top;
int main() {
n = read(), m = read();
for(int i = 1; i <= n; ++i) {
a[i] = read();
s[i] = s[i - 1] + a[i];
}
int t = 0;
for(int i = 1; i <= m; ++i) {
q[head = tail = 1] = 0;
t ^= 1;
memset(f[t], 0, sizeof f[t]);
for(int j = 1; j <= n; ++j) {
while(head < tail && slope(q[head], q[head + 1], f[t ^ 1]) <= s[j]) ++head;
f[t][j] = f[t ^ 1][q[head]] + (s[j] - s[q[head]]) * s[q[head]];
while(head < tail && slope(q[tail - 1], q[tail], f[t ^ 1]) > slope(q[tail - 1], j, f[t ^ 1]))--tail;
q[++tail] = j;
}
}
writeln(f[t][n]);
return 0;
}