洛谷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;
}