Luogu P3648 [APIO2014]序列分割 题解

Luogu P3648 [APIO2014]序列分割 题解

Describe

题目链接

你正在玩一个关于长度为 n 的非负整数序列的游戏。这个游戏中你需要把序列分成 k 1 个非空的块。为了得到 k 1 块，你需要重复下面的操作 k 次： 选择一个有超过一个元素的块（初始时你只有一块，即整个序列） 选择两个相邻元素把这个块从中间分开，得到两个非空的块。 每次操作后你将获得那两个新产生的块的元素和的乘积的分数。你想要最大化最后的总得分。 对于所有的数据，2leq n leq 100000,1leq k leq minleft(n-1,200right)。

Solution

。 上面那个式子就变成了：

f_i=max(g_k s_ktimes(s_i-s_k))(0leq j < k <i )

更优。

g_k s_ktimes(s_i-s_k) ge g_j s_jtimes(s_i-s_j)

化简一下，可得：

frac{(g_j-{s_j}^2)-(g_k-{s_k}^2)}{s_k-s_j}leq s_i

那么维护一个下凸壳即可。(注意分母可能为

Code

代码语言：javascript复制

#include<bits/stdc  .h>
#define LD double
using namespace std;
int n,k,a[100010],q[100010],pre[100010][210];
long long g[100010],f[100010],s[100010];
inline LD slope(int j,int k){
    return s[j]==s[k]?-2000000000.0:(LD)((LD)((g[j]-s[j]*s[j])-(g[k]-s[k]*s[k])))/((LD)(s[k]-s[j]));
}
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 t=1;t<=k;t  ){
        int l,r;l=r=1;q[1]=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][t]=q[l];
            while(l<r&&slope(q[r-1],q[r])>=slope(q[r],i)) --r;
            q[  r]=i;
        }
        for(int i=1;i<=n;i  ) g[i]=f[i];
    }
    printf("%lldn",f[n]);
    for(int i=k,t=n;i>=1;i--) t=pre[t][i],printf("%d ",t);printf("n");
}

游戏

0 人点赞