P3648-[APIO2014]序列分割
题目:
题目描述:
你正在玩一个关于长度为 $n$ 的非负整数序列的游戏。这个游戏中你需要把序列分成 $k + 1$ 个非空的块。为了得到 $k + 1$ 块，你需要重复下面的操作 $k$ 次：
选择一个有超过一个元素的块（初始时你只有一块，即整个序列）
选择两个相邻元素把这个块从中间分开，得到两个非空的块。
每次操作后你将获得那两个新产生的块的元素和的乘积的分数。你想要最大化最后的总得分。
输入格式:
第一行包含两个整数 $n$ 和 $k$。保证 $k + 1 \leq n$。
第二行包含 $n$ 个非负整数 $a_1, a_2, \cdots, a_n$ $(0 \leq a_i \leq 10^4)$，表示前文所述的序列。
输出格式:
第一行输出你能获得的最大总得分。
第二行输出 $k$ 个介于 $1$ 到 $n - 1$ 之间的整数，表示为了使得总得分最大，你每次操作中分开两个块的位置。第 $i$ 个整数 $s_i$ 表示第 $i$ 次操作将在 $s_i$ 和 $s_{i + 1}$ 之间把块分开。
如果有多种方案使得总得分最大，输出任意一种方案即可。
样例:
样例输入 1:
样例输出 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--;
}
}
|