洛谷3648 [APIO2014]序列分割

题意

你正在玩一个关于长度为 $n$ 的非负整数序列的游戏。这个游戏中你需要把序列分成 $k + 1$ 个非空的块。为了得到 $k + 1$ 块，你需要重复下面的操作 $k$ 次：

1. 选择一个有超过一个元素的块（初始时你只有一块，即整个序列）
2. 选择两个相邻元素把这个块从中间分开，得到两个非空的块。

每次操作后你将获得那两个新产生的块的元素和的乘积的分数。你想要最大化最后的总得分。

$n\le 100000 \ , \ k\le 200$ 。

题解

可以证明分割的顺序不会影响答案，不妨假设从右到左依次分割。

用 $f[i][j]$ 表示前 $i$ 个数，分割了 $j$ 次的最大得分；$S_i$ 为数列的前缀和。方程式为

$$f[i][j]=\max_k f[k][j-1]+(S_i-S_k)\times S_k$$

$${S_k}^2-f[k][j-1]=S_i\times S_k-f[i][j]$$

可以斜率优化，$S_i$ 显然单调。但因为数列可能有 $0$ ，所以需要对斜率除数为 $0$ 的情况特判。

因为只关心当前和上一层状态的值，所以开一个数组 $f[i][2]$ 和 $last=0,cur=1$ ，当前状态和上一层状态即为 $f[i][cur],f[i][last]$ ，每一层让 $last,cur$ 都 $xor \ 1$ 即可。

#include<bits/stdc++.h>
#define ll long long

using namespace std;

inline ll read()
{
    char ch=getchar(); ll f=1,x=0;
    while (ch<'0' || ch>'9') { if (ch=='-') f=-1; ch=getchar(); }
    while (ch>='0' && ch<='9') { x=x*10+ch-'0'; ch=getchar(); }
    return f*x;
}

const ll N=100005;
bool cur=1,last=0;
ll n,m,s[N],f[N][2],q[N],nxt[205][N];

inline double slope(ll x,ll y)
{
    if (s[x]==s[y]) return -1e9; //特判
    return (1.0*
            (s[x]*s[x]-f[x][last]-s[y]*s[y]+f[y][last])/
            (s[x]-s[y]));
}

signed main()
{
    n=read(); m=read();
    for (ll i=1;i<=n;i++) s[i]=s[i-1]+read();
    for (ll i=1;i<=m;i++)
    {
        ll l=1,r=1; q[1]=0;
        last^=1; cur^=1;
        for (ll j=1;j<=n;j++)
        {
            while (l<r && slope(q[l],q[l+1])<=s[j]) l++;
            f[j][cur]=f[q[l]][last]+s[q[l]]*(s[j]-s[q[l]]);
            nxt[i][j]=q[l];
            while (l<r && slope(q[r-1],q[r])>=slope(q[r],j)) r--;
            q[++r]=j;
        }
    }
    printf("%lld\n",f[n][cur]);
    for (ll i=m,j=nxt[i][n];i;i--,j=nxt[i][j]) printf("%lld ",j);
    return 0;
}