你正在玩一个关于长度为 n 的非负整数序列的游戏。这个游戏中你需要把序列分成 k+1 个非空的块。为了得到 k+1 块，你需要重复下面的操作 k 次：
选择一个有超过一个元素的块（初始时你只有一块，即整个序列）
选择两个相邻元素把这个块从中间分开，得到两个非空的块。
每次操作后你将获得那两个新产生的块的元素和的乘积的分数。你想要最大化最后的总得分。
第一行包含两个整数 n 和 k。保证 k+1≤n。
第二行包含 n 个非负整数 a1,a2,⋯,an (0≤ai≤104)，表示前文所述的序列。
第一行输出你能获得的最大总得分。
第二行输出 k 个介于 1 到 n−1 之间的整数，表示为了使得总得分最大，你每次操作中分开两个块的位置。第 i 个整数 si 表示第 i 次操作将在 si 和 si+1 之间把块分开。
如果有多种方案使得总得分最大，输出任意一种方案即可。
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
51
52
53
| #include "ybwhead/ios.h"
const int maxn = 5e5 + 10;
long long a[maxn], sum[maxn];
long long g[maxn], f[maxn];
#define Y(x) (g[x] - sum[x] * sum[x])
#define X(x) (-sum[x])
double slope(int x, int y)
{
if (sum[x] == sum[y])
return -1e18;
return (double)(Y(y) - Y(x)) / (X(y) - X(x));
}
int nxt[maxn][200];
int n, k;
int q[maxn];
int main()
{
yin >> n >> k;
for (int i = 1; i <= n; i++)
yin >> a[i], sum[i] = a[i] + sum[i - 1];
int l, r;
for (int xx = 1; xx <= k; xx++)
{
for (int i = 1; i <= n; i++)
g[i] = f[i];
l = 1;
r = 0;
for (int i = 1; i <= n; i++)
{
while (l < r && slope(q[l], q[l + 1]) <= sum[i])
++l;
f[i] = 0;
if (l <= r)
{
int tmp = q[l];
nxt[i][xx] = tmp;
f[i] = g[tmp] + sum[tmp] * (sum[i] - sum[tmp]);
// yout << g[tmp] << endl;
}
while (l < r && slope(q[r - 1], q[r]) >= slope(q[r], i))
--r;
q[++r] = i;
}
}
yout << f[n] << endl;
int tmp = n, kk = k;
while (kk)
{
tmp = nxt[tmp][kk];
yout << tmp << ' ';
kk--;
}
}
|
v1.4.14