征途（bzoj 4518）

Description

Pine开始了从S地到T地的征途。

从S地到T地的路可以划分成n段，相邻两段路的分界点设有休息站。

Pine计划用m天到达T地。除第m天外，每一天晚上Pine都必须在休息站过夜。所以，一段路必须在同一天中走完。

Pine希望每一天走的路长度尽可能相近，所以他希望每一天走的路的长度的方差尽可能小。

帮助Pine求出最小方差是多少。

设方差是v，可以证明，v×m^2是一个整数。为了避免精度误差，输出结果时输出v×m^2。

Input

第一行两个数 n、m。

第二行 n 个数，表示 n 段路的长度

Output

一个数，最小方差乘以 m^2 后的值

Sample Input

5 2
1 2 5 8 6

Sample Output

HINT

1≤n≤3000,保证从 S 到 T 的总路程不超过 30000

/*

  先吐槽一波数据，n=2146，只有2143个数的输入也是没谁了，害的我找了半天错误！

  设m天走过的路程分别是a1,a2...am，平均数为p=dis[n]/m

  化简一波式子 ans=Σ((ai-p)*(ai-p))*m*m=m*Σ(ai*ai)-dis[n]*dis[n]

  f[i][j]表示第i天走到j地的最小 Σai*ai

  首先求出动态转移方程 f[i][j]=min(f[i][k]+(dis[j]-dis[k])^2)

  可以斜率优化，化简上式可得，若k1比k2更优，则有：

  (dis[k1]^2-dis[k2]^2+f[i-1][k1]-f[i-1][k2])/(dis[k1]-dis[k2])>dis[j]*2

*/

#include<cstdio>

#include<iostream>

#include<cstring>

#define N 3010

#define lon long long

using namespace std;

lon dis[N],f[N][N];int n,m,q[N];

lon read(){

    lon num=,flag=;char c=getchar();

    while(c<''||c>''){if(c=='-')flag=-;c=getchar();}

    while(c>=''&&c<=''){num=num*+c-'';c=getchar();}

    return num*flag;

}

double lv(int i,int k1,int k2){

    return double(dis[k1]*dis[k1]-dis[k2]*dis[k2]+f[i-][k1]-f[i-][k2])/double(dis[k1]-dis[k2]);

}

int main(){

    scanf("%d%d",&n,&m);

    for(int i=;i<=n;i++){

        int x=;scanf("%d",&x);

        dis[i]=dis[i-]+(lon)x;

    }

    memset(f,/,sizeof(f));

    int h,t;f[][]=;

    for(int i=;i<=m;i++){

        h=;t=;q[]=;

        for(int j=;j<=n;j++){

            while(h<t&&lv(i,q[h+],q[h])<=dis[j]*)

                h++;

            f[i][j]=f[i-][q[h]]+(dis[j]-dis[q[h]])*(dis[j]-dis[q[h]]);

            while(h<t&&lv(i,j,q[t])<=lv(i,q[t],q[t-])) t--;

            q[++t]=j;

        }

    }

    cout<<f[m][n]*m-dis[n]*dis[n];

    return ;

}

巴特西