$$\Large\texttt{My Blog}$$


Description

题目链接:Luogu 3648

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

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

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

数据范围: $2\le n\le 10^5$ , $1\le k\le \min(n-1,200)$ , $0\le a_i\le 10^4$


Solution

我们首先证明答案和分割顺序无关

如果我们有长度为 $3$ 的序列 $x,y,z$ 将其分为 $3$ 部分,有如下两种分割方法:

  1. 先在 $x$ 后面分割,答案为 $x(y+z)+yz$ 即为 $xy+yz+zx$ 。
  2. 先在 $y$ 后面分割,答案为 $(x+y)z+xy$ 即为 $xy+yz+zx$ 。

然后这个结论可以扩展到任意长度的序列(分析一下贡献),证明完毕 QAQ

那么我们定义 $F_{i,j}$ 表示前 $i$ 个数进行 $j$ 次切割的最大得分。我们记 $a_i$ 的前缀和为 $s_i$ ,那么转移方程为: $$F_{i,k}=\max\{F_{j,k-1}+s_j(s_i-s_j)\}\quad (0\le j<i)$$ 为了方便表述,我们记 $F_{i,k}$ 为 $f_i$ , $F_{j,k-1}$ 为 $g_j$ ,相当于把 $F$ 的第二维滚动掉了。

那么方程为: $$f_i=\max\{g_j+s_j(s_i-s_j)\}\quad (0\le j<i)$$ 感觉是一个很显然的可以斜率优化的式子!

我们任取 $j,k$ 满足 $0\le k<j<i$ 且 $j$ 比 $k$ 更优,那么有如下不等式:

$$g_j+s_j(s_i-s_j)\ge g_k+s_k(s_i-s_k)$$ $$\frac{(g_j-{s_j}^2)-(g_k-{s_k}^2)}{s_k-s_j}\le s_i$$

维护一个下凸壳然后斜率优化即可。

注意:本题中 $a_i$ 是非负整数,所以 $s_k-s_j$ 可能等于 $0$ 。这种情况需要特判, $\text{slope}$ 需要返回 $-\text{INF}$ 。

时间复杂度: $O(nk)$ (貌似还可以凸优化?带权二分?)


Code

#include <cstdio>
#include <cstring>

const int N=1e5+5,M=205;
int n,k,a[N],q[N],pre[N][M];
long long s[N],f[N],g[N];

double slope(int i,int j) {
    if(s[i]==s[j]) return -1e18;
    return 1.0*((g[i]-s[i]*s[i])-(g[j]-s[j]*s[j]))/(s[j]-s[i]);
}
int main() {
    scanf("%d%d",&n,&k);
    for(int i=1;i<=n;++i) scanf("%d",&a[i]),s[i]=s[i-1]+a[i];
    for(int j=1;j<=k;++j) {
        int l=1,r=0;
        q[++r]=0;
        for(int i=1;i<=n;++i) {
            while(l<r&&slope(q[l],q[l+1])<=s[i]) ++l;
            f[i]=g[q[l]]+s[q[l]]*(s[i]-s[q[l]]);
            pre[i][j]=q[l];
            while(l<r&&slope(q[r-1],q[r])>=slope(q[r],i)) --r;
            q[++r]=i;
        }
        memcpy(g,f,sizeof(f));
    }
    printf("%lld\n",f[n]);
    for(int x=n,i=k;i>=1;--i) x=pre[x][i],printf("%d%c",x," \n"[i==1]);
    return 0;
}