首页 > Windows开发 > 详细

P3648 [APIO2014]序列分割(斜率优化dp)

时间:2019-04-22 20:55:42      阅读:48      评论:0      收藏:0      [点我收藏+]

标签:api   ostream   凸包   求解   ref   ble   urn   clu   影响   

P3648 [APIO2014]序列分割

我们先证明,分块的顺序对结果没有影响。

我们有一个长度为3的序列$abc$

现在我们将$a,b,c$分开来

随意枚举一种分块方法,如$(ab)(c)$,$(a)(b)(c)$

答案为$(a+b)*c+a*b=ac+bc+ab$

多枚举几种,我们发现答案总是不变的。

所以我们可以默认每次从左到右扫,用dp求解

对于每个$1$到$k$,我们都把序列扫一遍

设$f[k][i]$为对前$i$个数进行$k$次切割的最大价值,

$s[i]$为元素前缀和,那么

$f[k][i]=f[k-1][j]+s[j]*(s[i]-s[j])$

这个$k$显然是可以滚动优化掉的,设滚动数组为$g[i]$

$f[i]=g[j]+s[j]*(s[i]-s[j])$

$g[j]-s[j]^{2}=-s[i]*s[j]+f[i]$

又化成了我们熟悉的$y=kx+b$

$y=g[j]-s[j]^{2}$

$k=-s[i]$

$x=s[j]$

$b=f[i]$

$x,k$单调递增,于是我们直接上单调队列维护下凸包就好辣

顺带再开个数组记录一下路径就好了

#include<iostream>
#include<cstdio>
#include<cstring>
#define rint register int
using namespace std;
typedef long long ll;
#define N 100005
ll s[N],f[N],g[N];
int n,k,L,R,h[N],p[205][N];
inline ll X(int x){return s[x];}
inline ll Y(int x){return g[x]-s[x]*s[x];}
inline ll KK(ll xa,ll ya,ll xb,ll yb){return ya*xb-yb*xa;}
int main(){ 
    scanf("%d%d",&n,&k);
    for(rint i=1;i<=n;++i)
        scanf("%lld",&s[i]),s[i]+=s[i-1];
    for(rint j=1;j<=k;++j){
        h[L=R=1]=0;
        for(rint i=1;i<=n;++i){    
            while(L<R&&KK(X(h[L+1])-X(h[L]),Y(h[L+1])-Y(h[L]),1,-s[i])>=0) ++L;
            f[i]=g[h[L]]+(s[i]-s[h[L]])*s[h[L]]; p[j][i]=h[L];
            while(L<R&&KK(X(h[R])-X(i),Y(h[R])-Y(i),X(h[R])-X(h[R-1]),Y(h[R])-Y(h[R-1]))<=0) --R;
            h[++R]=i;
        }swap(g,f);
    }
    printf("%lld\n",g[n]);//注意答案在g上
    for(rint i=k,d=p[k][n];i;--i,d=p[i][d]) printf("%d ",d);
    return 0;
}

P3648 [APIO2014]序列分割(斜率优化dp)

标签:api   ostream   凸包   求解   ref   ble   urn   clu   影响   

原文:https://www.cnblogs.com/kafuuchino/p/10751996.html

(0)
(0)
   
举报
评论 一句话评论(0
0条  
登录后才能评论!
© 2014 bubuko.com 版权所有 鲁ICP备09046678号-4
打开技术之扣,分享程序人生!
             

鲁公网安备 37021202000002号