玄学，没有什么可说的。。。

 

delta一般是0.99多

初始温度T几千？

终止温度1e-10左右

SA次数大概6次

 

记住板子：

1.坐标的选择范围和温度有关

2.不优解的取舍和温度有关

3.只有取到更优解的时候才更新ans

4.取舍判断条件：

if(Delta<0){    //upda ans    //upda now}else if(exp(-Delta/T)*RAND_MAX>rand()) //upda now

这个exp(-Delta/T)是0~1之间的小数，Delta越小、T越大，值越大

 

IOI赛制多交几次就好了

 

例题： 

// luogu-judger-enable-o2#include
     
      #define il inline#define reg register int#define numb (ch^'0')using namespace std;typedef long long ll;il void rd(int &x){    char ch;bool fl=false;    while(!isdigit(ch=getchar()))(ch=='-')&&(fl=true);    for(x=numb;isdigit(ch=getchar());x=x*10+numb);    (fl==true)&&(x=-x);}namespace Miracle{const int N=1000+5;const double deta=0.995;int n;struct po{    double x,y;    double w;    po(){}    po(double xx,double yy){        x=xx;y=yy;w=0.0;    }}a[N];double dis(po a,po b){    return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));}double calc(double x,double y){    double ret=0;    for(reg i=1;i<=n;++i){        ret+=dis(a[i],po(x,y))*a[i].w;    }    return ret;}double ans;double sx,sy;double ax,ay;void SA(){    double x=sx,y=sy;    double T=2000;    while(T>1e-14){        double X=x+((rand()<<1)-RAND_MAX)*T;        double Y=y+((rand()<<1)-RAND_MAX)*T;        double tmp=calc(X,Y);        double cha=tmp-ans;        if(cha<0){            ans=tmp;            ax=X;ay=Y;            x=X;y=Y;        }        else if(exp(-cha/T)*RAND_MAX>rand()) x=X,y=Y;        T*=deta;    }}int main(){    srand(19260817);    rd(n);    for(reg i=1;i<=n;++i){        scanf("%lf%lf%lf",&a[i].x,&a[i].y,&a[i].w);        sx+=a[i].x,sy+=a[i].y;    }    ans=1e18;    sx/=n;sy/=n;    for(reg i=1;i<=10;++i){        SA();    }    printf("%.3lf %.3lf",ax,ay);    return 0;}    }signed main(){    Miracle::main();    return 0;}/*   Author: *Miracle*   Date: 2019/1/20 19:21:02*/
     

这个就是和DP结合

排列方式或者决策点可能不是最优的，但是calc得到的答案必须是精确的

所以要精确DP

这个是序列的SA

直接交换。

不行再换回来

 

至于最后为什么还要交换，可能考虑到总是可能差一点得到最优解吧。。。

#include
     
      using namespace std;typedef long long ll;const int N=22;const int M=8;const int inf=0x3f3f3f3f;const double eps=1e-10;int ans,a[N];int f[N][M];int n,m;int s[N];double delta=0.99;int dp(){    memset(f,0x3f,sizeof f);    memset(s,0,sizeof s);    f[0][0]=0;    for(int i=1;i<=n;i++){      s[i]=s[i-1]+a[i];      for(int k=1;k<=min(m,i);k++){          for(int j=0;j
      
       1e-14){        //cout<
       
        <
        
         rand()) haha++;        else swap(a[x],a[y]);        T*=delta;    }    for(int i=1;i<=n;i++){        for(int j=i+1;j<=n;j++){            swap(a[i],a[j]);            ans=min(ans,dp());            swap(a[i],a[j]);        }    }}void sol(){    ans=inf;    while((double)clock()/CLOCKS_PER_SEC<0.8) SA();}int main(){    srand(19260817);    scanf("%d%d",&n,&m);    int sum=0;    for(int i=1;i<=n;i++){        scanf("%d",&a[i]);        sum+=a[i];    }    sol();        double ave=(double)sum/(double)m;    double up=(double)ans-2*sum*ave+m*ave*ave;    //cout<
         
          <<" "<
          
           <<" "<
           
            <