[Sdoi2016]征途

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

36

HINT

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

忘了附题解：

式子拆开后等于

m*∑xi^2 - sum^2

所以写出dp方程：

f[i][j]=f[i-1][k]+(s[j]-s[k])^2

于是直接斜率优化

 #include<iostream>

 #include<cstdio>

 #include<algorithm>

 #include<cstring>

 using namespace std;

 int s[],f[][],q[],head,tail,n,m,ans=2e9;

 double A(int i, int p)

 {

   return (double)f[p][i] + s[i]*s[i];

 }

 double slope(int j,int k,int p)

 {

     return (double)(A(j,p)-A(k,p))/(double)(s[j]-s[k]);

 }

 int main()

 {int i,j;

   cin>>n>>m;

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

     scanf("%d",&s[i]),s[i]+=s[i-];

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

     f[][i]=s[i]*s[i];

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

     {

       head=;tail=;

       q[]=i-;

       for (j=i;j<=n;j++)

     {

       while (head<tail&&slope(q[head],q[head+],i-)<=2.0*s[j]) head++;

       f[i][j]=f[i-][q[head]]+(s[q[head]]-s[j])*(s[q[head]]-s[j]);

       while (head<tail&&slope(q[tail-],q[tail],i-)>=slope(q[tail],j,i-)) tail--;

       tail++;

       q[tail]=j;

      }

     }

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

 }