传送门
大难不死，必有后福
自从在空间里大骂后
十分钟过了两道调了两天的题……
解题思路
非常经典的一个对序列进行模拟退火的题。
求方差时直接用公式就行（平均数一开始可以预处理出来）
求分组后最小的方差需要用到dp。
dp[i][j]表示前i个数分j组的方差。
直接枚举k转移即可。
注意事项
double类型的数组用memset初始化：
0x7f--一个很大的数
0x3f--一个很小的数(<1)
AC代码
#include<cstdio>
#include<iostream>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<ctime>
#include<iomanip>
#include<cstdlib>
using namespace std;
const double delta=0.996;
int n,m,a[25],d[25];
double ans=1e18,suma,dp[25][25];
double cal(){
memset(dp,0x7f,sizeof(dp));
dp[0][0]=0;
for(int i=1;i<=n;i++) d[i]=d[i-1]+a[i];
for(int i=1;i<=n;i++){
for(int j=1;j<=min(i,m);j++){
for(int k=0;k<i;k++){
dp[i][j]=min(dp[i][j],dp[k][j-1]+((d[i]-d[k])-suma/m)*((d[i]-d[k])-suma/m));
}
}
}
return dp[n][m];
}
void SA(){
ans=min(ans,cal());
double t=3000;
while(t>1e-15){
int x=rand()%n+1,y=rand()%n+1;
if(x==y) continue;
swap(a[x],a[y]);
double res=cal();
double cha=res-ans;
if(cha<0) ans=res;
else{
if(exp(-cha/t)*RAND_MAX<rand()) swap(a[x],a[y]);
}
t*=delta;
}
}
int main(){
srand(time(0));
srand(rand());
srand(rand());
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++) scanf("%d",&a[i]),suma+=a[i];
while((double)clock()/CLOCKS_PER_SEC<0.8) SA();
printf("%.2lf",sqrt(ans/m));
return 0;
}