P3648 [APIO2014]序列分割
首先发现一个性质，答案只和如何划分有关，和划分的顺序无关。用数学归纳法证明如下：
- 划分一次时，只有一种划分顺序；
- 划分两次时，设当前序列为 $a, b, c$ ，其中 $a, b, c$ 均为一段序列，需要在 $a, b$ 间和 $b, c$ 间划分。先在 $a, b$ 间划分，再在 $b, c$ 间划分的得分为 $a (b + c) +bc = ab + ac +bc$ ；先在 $b, c$ 间划分，再在 $a, b$ 间划分的得分为 $c(a + b) + ab = ab + ac +bc$ 。此时成立。
- 划分 $k + 1$ 次时，已划分的 $k$ 次，任意两种划分一定有 $k - 1$ 个是相同的，对答案的贡献相同，再划分两次，依然是相同的。
因此答案只和如何划分有关，我们对答案的计算进行规范化，使得从后向前划分，于是可以得到，第 $k$ 个数后如果要划分对序列 $1\ldots i$ 的贡献为 $s _ k (s _ i - s _ k)$ 。$f _ {i, j}$ 表示序列 $1\ldots i$ 中划分 $j$ 个数的最大得分，则有
$$
f _ {i, j} = \max _ {k < i} \{ f _ {k, j - 1} + s _ k (s _ i - s _ 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
| #include <cstdio>
#include <algorithm>
using namespace std;
typedef long long LL;
const int N = 1e5 + 10, M = 210;
LL s[N], f[N][M];
int n, m, pre[N][M];
int main()
{
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++)
{
scanf("%lld", &s[i]);
s[i] += s[i - 1];
}
for (int j = 1; j <= m; j++)
for (int i = 1; i <= n; i++)
for (int k = 1; k < i; k++)
{
LL t = f[k][j - 1] + s[k] * (s[i] - s[k]);
if (t >= f[i][j])
{
pre[i][j] = k;
f[i][j] = t;
}
}
printf("%lld\n", f[n][m]);
for (int i = pre[n][m]; m; i = pre[i][--m])
printf("%d ", i);
return 0;
}
|
此式显然可以斜率优化，即
$$
f _ {i, j} = \max _ {k < i} \{ f _ {k, j - 1} - s _ k ^ 2 +s _ k s _ i \}
$$
查看代码
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
| #include <cstdio>
#include <algorithm>
using namespace std;
typedef long long LL;
const LL inf = 1e18;
const int N = 1e5 + 10, M = 210;
LL s[N], f[N][M];
int hd, tl, q[N];
int n, m, pre[N][M];
double slp(int x, int a, int b)
{
if (s[a] == s[b])
return inf;
return (double)(f[a][x] - s[a] * s[a] - f[b][x] + s[b] * s[b]) / (double)(s[a] - s[b]);
}
int main()
{
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++)
{
scanf("%lld", &s[i]);
s[i] += s[i - 1];
}
for (int j = 1; j <= m; j++)
{
hd = 1, tl = 0;
for (int i = j; i <= n; i++)
{
while (hd < tl && slp(j - 1, q[hd], q[hd + 1]) > -s[i])
hd++;
pre[i][j] = q[hd];
f[i][j] = f[q[hd]][j - 1] + s[q[hd]] * (s[i] - s[q[hd]]);
while (hd < tl && slp(j - 1, q[tl], q[tl - 1]) < slp(j - 1, q[tl], i))
tl--;
q[++tl] = i;
}
}
printf("%lld\n", f[n][m]);
for (int i = pre[n][m]; m; i = pre[i][--m])
printf("%d ", i);
return 0;
}
|