[SDOI2016]征途

洛咕

题意:把长度为(n(n<=3000))的序列分成m段,使得每一段序列的和的方差(v)尽可能小,输出(v*m^2).

分析:本题难点在于方差公式???只要把方差列出来就很裸的斜率优化了.

若一个序列有n个数,每个数是(x_i),平均数是M,则该序列的方差

故本题中方差(v=frac{sum_{i=1}^{m}(a_i-ave)^2}{m}),其中(a_i)表示第i段的和,ave表示平均数,显然,(ave=frac{sum[n]}{m}).

故本题答案就是(ans=v*m^2=m*(sum_{i=1}^{m}(a_i-frac{sum[n]}{m})^2)),把累加拆开,就得到(ans=m*sum_{i=1}^ma_i^2-sum[n]^2),(sum[n]^2)和(m)都是已知量,故我们只要考虑如何最小化(sum_{i=1}^ma_i^2).

设(f[j][i])表示把前i个数分成j段,且(sum_{p=1}^ja[p]^2)最小.

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

设l<k且k比l更优,即

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

整理一下这个式子得到,

(frac{f[j-1][k]+sum[k]^2-f[j-1][l]-sum[l]^2}{sum[k]-sum[l]}<2*sum[i])

妥妥地斜率优化.

#include<bits/stdc++.h>
using namespace std;
inline int read(){
   int s=0,w=1;char ch=getchar();
   while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
   while(ch>='0'&&ch<='9'){s=s*10+ch-'0';ch=getchar();}
   return s*w;
}
const int N=3005;
int a[N],sum[N],q[N];
long long f[N][N];
inline double Count(int i,int j,int k){return 1.0*(f[i][j]+sum[j]*sum[j]-f[i][k]-sum[k]*sum[k])/(double)(sum[j]-sum[k]);}
int main(){
    int n=read(),m=read();
    for(int i=1;i<=n;i++)a[i]=read(),sum[i]=sum[i-1]+a[i];
    for(int i=1;i<=n;i++)f[1][i]=sum[i]*sum[i];
    for(int j=2;j<=m;j++){
		int l=1,r=1;q[1]=0;
		for(int i=1;i<=n;i++){
	    	while(l<r&&Count(j-1,q[l+1],q[l])<=2*sum[i])l++;
	    	f[j][i]=f[j-1][q[l]]+(sum[i]-sum[q[l]])*(sum[i]-sum[q[l]]);
	    	while(l<r&&Count(j-1,q[r],q[r-1])>=Count(j-1,i,q[r]))r--;
	    	q[++r]=i;
		}
    }
    printf("%lld
",m*f[m][n]-sum[n]*sum[n]);
    return 0;
}