「APIO 2014」Split the Sequence

发表于 | | 阅读次数:
字数统计: 355 字

Description

题目链接：UOJ 104

你正在玩一个关于长度为 $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}​$ 为 $f_i​$，$F_{j,k-1}​$ 为 $g_j​$，相当于把 $F​$ 的第二维滚动掉了。

那么方程为：

感觉是一个很显然的可以斜率优化的式子！

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

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

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

时间复杂度：$O(nk)$（貌似还可以凸优化？带权二分？）

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
 
#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;
}
0%