2428 - [HAOI2006]均分数据

题解bymod998244353

这题如果连续分组，就很简单： f[i][j]表示前i个数分了j组，则有：

f[i][j]=f[k][j-1]+(s[i]-s[k]-ave)*(s[i]-s[k]-ave)

其中s[i]为序列前缀和，ave为每组平均数。

不连续只要套个模拟退火就行了。

#include<bits/stdc++.h>
using namespace std;
const int MAXN=64;
int a[MAXN],n,m,s[MAXN];
double f[MAXN][MAXN],ans,ave;
double calc() {
	memset(f,127,sizeof(f));
	for(int i=1; i<=n; ++i)s[i]=s[i-1]+a[i];
	f[0][0]=0;
	for(int i=1; i<=n; ++i)
		for(int j=1; j<=i; ++j)
			for(int k=0; k<i; ++k)
				f[i][j]=min(f[i][j],f[k][j-1]+(s[i]-s[k]-ave)*(s[i]-s[k]-ave));
	return f[n][m];
}
void sa() {
	for(double t=3000; t>=1e-14; t*=0.996) {
		int x=rand()%(n-1)+1,y=rand()%(n-x)+x+1;
		swap(a[x],a[y]);
		double tmp=calc(),de=tmp-ans;
		if(de<0)ans=tmp;
		else if(exp(-de/t)*RAND_MAX<=rand())
			swap(a[x],a[y]);
	}
}
int main() {
	srand(time(0));
	scanf("%d%d",&n,&m);
	for(int i=1; i<=n; ++i) scanf("%d",&a[i]),ave+=a[i];
	ave/=m;
	ans=calc();
	int cnt=0;
	do sa();
	while(++cnt<10);
	printf("%.2lf\n",sqrt(ans/m));
	return 0;
}