bzoj4518--斜率優化DP，bzoj4518--斜率dp

bzoj4518--斜率優化DP，bzoj4518--斜率dp

設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

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

由於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;
}