题目概述

把 $n$ 个数分成 $m$ 份，求最小的均方差 $\sqrt{\sum_{i=1}^m(sum_i-ave)\over m}$ ，其中 $ave={\sum_{i=1}^{n}a_i\over m}$ ，$sum_i$ 为第 $i$ 组 $a$ 的和。

解题报告

之前好像很自信的写了个DFS+剪枝，然后就TLE了……

应该用模拟退火？说实话我不知道我是怎么过的，调参调着调着就过了QAQ。

我的做法大概就是温度越大，交换数组元素越频繁，求一个数组（有序）的最小均方差用DP，然后在退火之前先random_shuffle一下搞个比较正常的解……

示例程序

#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
using namespace std;
const int maxn=20,maxk=6;
typedef long double DB;

int n,m,a[maxn+5],MIN[maxn+5];DB ave,ans;

inline DB sqr(DB x) {return x*x;}
inline DB getsum(int *a){
    static DB f[maxn+5][maxk+5],sum[maxn+5]={0};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<=m;j++) f[i][j]=1e100;f[0][0]=0;
    for (int i=1;i<=n;i++)
        for (int j=0;j<i;j++)
            for (int k=1;k<=i&&k<=m;k++)
                f[i][k]=min(f[i][k],f[j][k-1]+sqr(sum[i]-sum[j]-ave));
    return sqrt(f[n][m]/m);
}
inline void Copy(int *a,int *b) {for (int i=1;i<=n;i++) a[i]=b[i];}
#define Rand() ((DB)rand()/RAND_MAX)
inline void Solve(DB T){
    static int now[maxn+5],tem[maxn+5];Copy(now,MIN);
    for (DB sum;T>1e-5;T*=0.995){
        Copy(tem,now);for (int t=ceil(T/2333*n);t;t--) swap(tem[rand()%n+1],tem[rand()%n+1]);
        sum=getsum(tem);if (sum<ans) ans=sum,Copy(MIN,tem),Copy(now,tem);
        else if (exp((ans-sum)/T)>Rand()) Copy(now,tem);
    }
}
int main(){
    freopen("program.in","r",stdin);freopen("program.out","w",stdout);
    scanf("%d%d",&n,&m);for (int i=1;i<=n;i++) scanf("%d",&a[i]),ave+=a[i];
    ave/=m;ans=getsum(a);Copy(MIN,a);
    for (int t=1;t<=1000;t++){
        random_shuffle(a+1,a+1+n);DB sum=getsum(a);
        if (sum<ans) ans=sum,Copy(MIN,a);
    }srand(19260817);for (int t=1;t<=10;t++) Solve(2333);
    printf("%.2f\n",(double)ans);return 0;
}