P3648 [APIO2014]序列分割

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\dots i$ 的贡献为 $s_k(s_i-s_k)$ 。$f_{i,j}$ 表示序列 $1\dots i$ 中划分 $j$ 个数的最大得分，则有
$$f_{i,j}=\underset{k<i}{max}\{f_{k,j-1}+s_k(s_i-s_k)\}$$
同时记录转移的来源，还原回去即可得到构造的方案。

查看代码

#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}=\underset{k<i}{max}\{f_{k,j-1}-s_k^2+s_k{s}_i\}$$

查看代码

#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;
}