Archie

怎样用模拟退火搞序列

随机交换就可以了

dp检查

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
using namespace std;
int n,m;int a[50],na[50];
double t;double ans=1e18;
double delat=0.996;
double dp[50][50];
double sum[50];
double work(){
    memset(dp,0x7f,sizeof(dp));
    dp[0][0]=0;
    sum[1]=na[1];
    for(int i=2;i<=n;++i)
    sum[i]=sum[i-1]+na[i];
    for(int i=1;i<=n;++i){
        for(int j=1;j<=min(m,i);++j){
            for(int z=0;z<i;++z){
                dp[i][j]=min(dp[i][j],dp[z][j-1]+((sum[i]-sum[z])-sum[n]/m)*((sum[i]-sum[z])-sum[n]/m));
            }   
        } 
    }
    return dp[n][m];
}
void sa(){
    double nans=ans;
    for(int i=1;i<=n;++i){
        na[i]=a[i];
    }
    t=2000;
    while(t>1e-15){
        int nx=rand()%n+1;
        int ny=rand()%n+1;
        if(nx==ny)
         continue;
        swap(na[nx],na[ny]);
        double res=work();
        //cout<<res<<endl;
        double key=res-nans;
        if(key<0){
            nans=res;
            ans=res;
            for(int i=1;i<=n;++i){
                a[i]=na[i];
            }
        }else{
            if(exp(-res/delat)*RAND_MAX<rand())
            swap(na[nx],na[ny]);
            else
            nans=res;
        }
        t*=delat;
    }
}
int main(){
    srand(20040519);
    srand(rand());
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;++i){
        scanf("%d",&a[i]);
    } 
    for(int i=1;i<=6;++i){
        sa();
        //printf("%.2lfn",ans);
    }
    printf("%.2lf",sqrt(ans/m));
    return 0;
}