[HAOI2006]均分数据

洛咕

题意:已知(n(n<=20))个正整数：(a_1,a_2,……,a_n) .今要将它们分成(m(2<=m<=6))组，使得各组数据的数值和最平均，即各组的均方差最小.均方差公式如下：

分析:首先根据公式各组数据和的平均值是(ave)已知的,即((sum_{i=1}^na[i])/m),所以要最小化均方差,我们只需要最小化(sum_{i=1}^m(sum_i-ave)^2)就好了,其中(sum_i)表示分成的第i段的和,这个显然是可以(dp)求的.设(f[i][j])表示将序列前i个数分成j段,(sum_{i=1}^j(sum_i-ave)^2)的最小值.那么(f[i][j]=min(f[i][j],f[k][j-1]+(s[i]-s[k]-avs)^2)),其中(s[])表示序列的前缀和.

那么现在的问题就是如何找到"序列"呢?因为根据题意这n个正整数是可以任意排列的.所以就要用到模拟退火来随机出排列.

这道题的各种参数还比较好调,一下就过去了.

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<queue>
#include<map>
#include<set>
#define ll long long
using namespace std;
inline int read(){
    int x=0,o=1;char ch=getchar();
    while(ch!='-'&&(ch<'0'||ch>'9'))ch=getchar();
    if(ch=='-')o=-1,ch=getchar();
    while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
    return x*o;
}
const int N=21;
int n,m,tot,a[N],sum[N];
double ave,ans,f[N][8];
inline double dp(){
	for(int i=1;i<=n;++i)sum[i]=sum[i-1]+a[i];//预处理前缀和
	for(int i=0;i<=n;++i)for(int j=0;j<=n;++j)f[i][j]=0x3f;
	f[0][0]=0;//初始化,其余为无穷大值
	for(int i=1;i<=n;++i){
		for(int j=1;j<=m;++j){
			for(int k=0;k<i;++k)
				f[i][j]=min(f[i][j],f[k][j-1]+(sum[i]-sum[k]-ave)*(sum[i]-sum[k]-ave));
		}
	}
	return (double)sqrt(f[n][m]*1.0/m);//根据公式来求均方差
}
inline void mnth(){
	double T=2333,eps=1e-6;
	while(T>eps){
		int x=rand()%n+1,y=rand()%n+1;//随机出两个数组下标
		if(x==y){T*=0.998;continue;}
		swap(a[x],a[y]);
		double now=dp(),delta=now-ans;
		if(delta<0)ans=now;
		else if(exp(-delta/T)*RAND_MAX>rand())ans=now;
		else swap(a[x],a[y]);//不能更新答案的话记得换回来
		T*=0.998;
	}
}
int main(){
	srand((int)time(NULL));n=read();m=read();
	for(int i=1;i<=n;++i)a[i]=read(),tot+=a[i];
	ave=(double)tot*1.0/m;ans=dp();mnth();printf("%.2lf
",ans);
    return 0;
}