征途

 

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

 

sol：写的我脑袋好疼啊qaq

对于斜率优化dp的题永远只会先写暴力qaq

#include 
      
       using namespace std;typedef long long ll;inline ll read(){    ll s=0;    bool f=0;    char ch=' ';    while(!isdigit(ch))    {        f|=(ch=='-'); ch=getchar();    }    while(isdigit(ch))    {        s=(s<<3)+(s<<1)+(ch^48); ch=getchar();    }    return (f)?(-s):(s);}#define R(x) x=read()inline void write(ll x){    if(x<0)    {        putchar('-'); x=-x;    }    if(x<10)    {        putchar(x+'0'); return;    }    write(x/10);    putchar((x%10)+'0');    return;}#define W(x) write(x),putchar(' ')#define Wl(x) write(x),putchar('\n')const int N=3005;int n,m;ll a[N],Qzh[N];ll dp[N][N];inline ll Sqr(ll x){    return x*x;}/*原式:Ans=(S1-Sum/m)^2+(S2-Sum/m)^2+...+(Sm-Sum/m)^2)/m*m*m---> Ans=m*(S1-Sum/m)^2+(S2-Sum/m)^2+...+(Sm-Sum/m)^2)---> Ans=m*((S1^2+S2^2+...+Sm^2)-2*(S1+S2+...Sm)*Sum/m+m*Sum*Sum/m/m)---> Ans=m*(S1^2+S2^2+...Sm^2)-2*Sum*Sum+m*Sum*Sum/m---> Ans=m*(S1^2+S2^2+...Sm^2)-Sum*Sum无视掉后面的常数 Sum*Sum可以得到当S1^2+S2^2+...+Sn^2最小的时候是最优的*/int main(){    int i,j,k;    R(n); R(m);    for(i=1;i<=n;i++) R(a[i]);    for(i=1;i<=n;i++) Qzh[i]=Qzh[i-1]+a[i];    memset(dp,63,sizeof dp);    dp[0][0]=0;    for(i=1;i<=n;i++)    {        for(j=1;j<=min(m,i);j++)        {            for(k=j-1;k<=i-1;k++)            {                dp[i][j]=min(dp[i][j],dp[k][j-1]+Sqr(Qzh[i]-Qzh[k]));            }        }    }//    printf("dp[%d][%d]=%lld\n",n,m,dp[n][m]);    Wl(dp[n][m]*m-Sqr(Qzh[n]));    return 0;}/*input5 21 2 5 8 6output36*/
      

然后我偷懒了，不写过程了，所有过程都在代码上面有（其实是因为找不到草稿纸滑稽）

/*原式:Ans=(S1-Sum/m)^2+(S2-Sum/m)^2+...+(Sm-Sum/m)^2)/m*m*m---> Ans=m*(S1-Sum/m)^2+(S2-Sum/m)^2+...+(Sm-Sum/m)^2)---> Ans=m*((S1^2+S2^2+...+Sm^2)-2*(S1+S2+...Sm)*Sum/m+m*Sum*Sum/m/m)---> Ans=m*(S1^2+S2^2+...Sm^2)-2*Sum*Sum+m*Sum*Sum/m---> Ans=m*(S1^2+S2^2+...Sm^2)-Sum*Sum无视掉后面的常数 Sum*Sum可以得到当S1^2+S2^2+...+Sn^2最小的时候是最优的然后就是斜率优化dp板子了吧qaqdp[i][j]表示到第i位,走了j天的最小平方和i,j,k (i
      
       
         dp[i][o-1]+Qzh[k]*Qzh[k]-2*Qzh[k]*Qzh[i]+Qzh[i]*Qzh[i] <= dp[j][o-1]+Qzh[k]*Qzh[k]-2*Qzh[k]*Qzh[j]+Qzh[j]*Qzh[j]--> dp[i][o-1]-dp[j][o-1]-2*Qzh[k]*(Qzh[i]-Qzh[j]) <= Qzh[j]*Qzh[j]-Qzh[i]*Qzh[i]见1),2),3) 可能只有3)是有用的 1)--> dp[i][o-1]-dp[j][o-1]+Qzh[i]*Qzh[i]-Qzh[j]*Qzh[j] <= 2*(Qzh[i]-Qzh[j])*Qzh[k]--> (dp[i][o-1]-dp[j][o-1]+Qzh[i]*Qzh[i]-Qzh[j]*Qzh[j])/(2*(Qzh[i]-Qzh[j])) >= Qzh[k] (注意Qzh[i]
        
          dp[i][o-1]-dp[j][o-1] <= (Qzh[j]+Qzh[i])*(Qzh[j]-Qzh[i])-2*Qzh[k]*(Qzh[j]-Qzh[i])--> dp[i][o-1]-dp[j][o-1] <= (Qzh[j]+Qzh[i]-2*Qzh[k])*(Qzh[j]-Qzh[i])即当 dp[i][o-1]-dp[j][o-1] <= (Qzh[j]+Qzh[i]-2*Qzh[k])*(Qzh[j]-Qzh[i]) i比j优,否则j比i优3)--> dp[i][o-1]+Qzh[i]*Qzh[i]-dp[j][o-1]-Qzh[j]*Qzh[j] <= 2*Qzh[k]*(Qzh[i]-Qzh[j])所以i
         
          
           =G[j][k]时j就没用了Ps:以上全部在i
           
            
             using namespace std;typedef long long ll;inline ll read(){ ll s=0; bool f=0; char ch=' '; while(!isdigit(ch)) { f|=(ch=='-'); ch=getchar(); } while(isdigit(ch)) { s=(s<<3)+(s<<1)+(ch^48); ch=getchar(); } return (f)?(-s):(s);}#define R(x) x=read()inline void write(ll x){ if(x<0) { putchar('-'); x=-x; } if(x<10) { putchar(x+'0'); return; } write(x/10); putchar((x%10)+'0'); return;}#define W(x) write(x),putchar(' ')#define Wl(x) write(x),putchar('\n')const int N=3005;int n,m;ll a[N],Qzh[N];ll dp[N][N];int Queue[N];//满足dp[i][o-1]+Qzh[i]*Qzh[i]-dp[j][o-1]-Qzh[j]*Qzh[j] <= Qzh[k]*2*(Qzh[i]-Qzh[j])则i比j优 inline bool Pand(int i,int j,int k,int o) //i
             
              
               =S2)?1:0;}int main(){ int i,j,k; R(n); R(m); for(i=1;i<=n;i++) R(a[i]); for(i=1;i<=n;i++) Qzh[i]=Qzh[i-1]+a[i]; for(i=1;i<=n;i++) dp[i][1]=Qzh[i]*Qzh[i]; for(i=2;i<=m;i++) { int Head=0,Tail=0; Queue[0]=0; for(j=1;j<=n;j++) { while(Head