bzoj4518 [ SDOI2016 ] --斜率优化DP

2018-06-17 23:39:13来源:未知 阅读 ()

新老客户大回馈,云服务器低至5折

设x[i]为第i天走的路程,s为路程总和,则:

ans=[(s/m-x[1])^2+(s/m-x[2])^2+(s/m-x[3])^2+...+(s/m-x[m])^2]*m

     =[(s-x[1]*m)^2+(s-x[2]*m)^2+(s-x[3]*m)^2]+...+(s-x[m]*m)^2)]/m

     =s^2+m*(x[1]^2+x[2]^2+x[3]^2+...+x[m]^2)-2*(x[1]+x[2]+x[3]+...+x[m])*s

     =m*(x[1]^2+x[2]^2+x[3]^2+...+x[m]^2)-s^2

由于m,s不变,问题可以转化为将一个长为n的序列划分成m段,求最小平方和

令f[i][j]为将长为j的序列划分成i段的最小平方和,则

f[i][j]=min(f[i][k]+(sum[j]-sum[k])^2),0<k<j

很明显的斜率优化。

 

斜率优化过程如下:

设p<k<j,在求f[i][j]时k比p优,于是可得如下方程:
f[i-1][k]+(sum[j]-sum[k])^2<f[i-1][p]+(sum[j]-sum[p])^2

f[i-1][k]+sum[k]^2-(f[i-1][p]+sum[p]^2)<2*(sum[k]-sum[p])*sum[j]

(f[i-1][k]+sum[k]^2-(f[i-1][p]+sum[p]^2))/(2*sum[k]-2*sum[p])<sum[j]

如果令y[i-1][t]=f[i-1][t]+sum[t]^2,x[i-1][t]=2*sum[t],

则原式可化为:(y[i-1][k]-y[i-1][p])/(x[i-1][k]-x[i-1][p])<sum[j],不就是线段kp的斜率小于sum[j]吗?

令g[i][j](i>j)为线段ij的斜率。

于是在求f[i]时维护一个序列,满足对任意j(j>2),g[j][j-1]>g[j-1][j-2],则f[i][j]的最优值就从序列中斜率小于sum[j]的序号最大的线段的右端点转移。

时间复杂度从O(n*n*m)降到O(n*m)

 

代码:

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
#define ll long long
ll i,j,k,n,m,f[3001][3001],x[3001],y[3001][3001],sum[3001],s,l,r,q[3001];
int main()
{
    scanf("%d%d",&n,&m);
    for(i=1;i<=n;i++)scanf("%lld",&sum[i]),s+=sum[i],sum[i]+=sum[i-1],x[i]=sum[i]<<1,f[1][i]=sum[i]*sum[i],y[1][i]=f[1][i]<<1;
    for(i=2;i<=m;i++){
        l=r=0;
        for(j=1;j<=n;j++){
            while(l<r&&y[i-1][q[l+1]]-y[i-1][q[l]]<=sum[j]*(x[q[l+1]]-x[q[l]]))l++;
            f[i][j]=f[i-1][q[l]]+(sum[j]-sum[q[l]])*(sum[j]-sum[q[l]]);
            y[i][j]=f[i][j]+sum[j]*sum[j];
            while(l<r&&(x[q[r]]-x[q[r-1]])*(y[i-1][j]-y[i-1][q[r-1]])<=(x[j]-x[q[r-1]])*(y[i-1][q[r]]-y[i-1][q[r-1]]))r--;
            q[++r]=j;
        }
    }
    printf("%lld\n",f[m][n]*m-s*s);
    return 0;
}
bzoj4518

 

标签:

版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有

上一篇:HDU 5475(2015 ICPC上海站网络赛)--- An easy problem(线段

下一篇:Codeforces Round #234A