洛谷P3648 [APIO2014] 序列分割题解

题目链接：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}$ 之间把块分开。

如果有多种方案使得总得分最大，输出任意一种方案即可。

数据范围：

$2 \leq n \leq 100000, 1 \leq k \leq \min\{n - 1, 200\}$。

不难发现，总得分与切的顺序无关，只与切的位置有关。

设某方案切出来三段 $A,B,C$ ，先切 $AB$ 和先切 $BC$ 的得分分别为

$A(B+C) + BC = (A+B)C + AB$

因为限制刀数，所以很容易设计出dp方程。

设 $f_{i,j}$ 表示考虑前 $i$ 个数，切了 $j$ 刀的最大得分，则

$f_{i,j} = \max_{1\le k < j} \{f_{i-1,k} + S_k(S_j-S_k)\}$

其中 $S_i = \sum_{j=1}^ia_j$ 。

观察~~数据范围~~和转移方程，可以发现这个柿子可以斜率优化

考虑比 $k$ 更优的 $l$ ， $0\le k < l <j$

显然 $S_k < S_l$ ，则

$f_{i-1,k} + S_j S_k - S_k^2 < f_{i-1,l} + S_j S_l - S_l^2$

化简可得

$\frac{(S_l^2 - f_{i-1,l}) - (S_k^2 - f_{i-1,k})}{S_l - S_k} < S_j$

记 $y_l = S_l^2 - f_{i-1,l},~x_l=S_l$ ，那么就是熟悉的 $\dfrac{y_l-y_k}{x_l-x_k} < k$ 的形式啦

时间复杂度 $O(nm)$

代码：（~~啥时候才能完全记住斜率优化板子啊~~）

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cstdarg>
#include <cmath>
#include <iomanip>
#include <random>
#include <queue>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
#define N ((int)(1e5+15))

int n,m,st,en,p,s[N],f[2][N],q[N],last[205][N];
#define y(_) (s[_] * s[_] - f[(i ^ 1) & 1][_])
#define x(_) (s[_])
bool test1(int i,int j,int k)
{
    int u=q[k],v=q[k+1];
    return y(v)-y(u) <= s[j] * (x(v) - x(u));
}
bool test2(int i,int j,int k)
{
    int u=q[k-1],v=q[k];
    return (y(j)-y(v)) * (x(v)-x(u)) <= (x(j)-x(v)) * (y(v)-y(u));
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    cin >> n >> m;
    for(int i=1; i<=n; i++)
        cin >> s[i], s[i] += s[i-1];
    for(int i=1; i<=m; i++)
    {
        q[st=en=1]=0;
        int now=i&1,pre=now^1,l;
        for(int j=1; j<=n; j++)
        {
            while(st<en && test1(i,j,st)) ++st;
            // 斜率优化最优的点是q[st] !!!，不是q[st+1] !!!
            last[i][j] = l = q[st]; 
            f[now][j] = f[pre][l] + (s[j] - s[l]) * s[l];
            while(st<en && test2(i,j,en)) --en;
            q[++en]=j;
        }
    }
    cout << f[m&1][p=n] << '\n';
    vector<int> v;
    for(int i=m; i; i--) v.push_back(p=last[i][p]);
    for(int i=m-1; i>=0; i--) cout << v[i] << " \n"[!i];
    return 0;
}