求助此题模拟退火做法(悬赏一关)
  • 板块题目总版
  • 楼主hundunqidian
  • 当前回复1
  • 已保存回复1
  • 发布时间2023/10/31 21:40
  • 上次更新2023/11/4 13:16:33
查看原帖
求助此题模拟退火做法(悬赏一关)
398310
hundunqidian楼主2023/10/31 21:40

模拟赛时做法↓(但是WA 0pts)

#include<bits/stdc++.h>
#define int long long
using namespace std;
inline void rd(int &r){
	int x=0,f=1;
	char ch=getchar();
	while(ch<'0' || '9'<ch){
		if(ch=='-'){
			f=-f;
		}
		ch=getchar();
	}
	while('0'<=ch && ch<='9'){
		x=(x<<3)+(x<<1)+ch-48;
		ch=getchar();
	}
	r=x*f;
	return ;
}
inline void out(int x){
	if(x<0) x=-x,putchar('-');
	if(x>9) out(x/10);
	putchar(x%10+'0');
	return ;
}
int const X=100;
int n;
int p[X],q[X],r[X],s[X];
int num[X],rem[X];
inline int pf(int x){
	return x*x;
}
inline int suan(){
	int res=0;
	int L[X]={0},R[X]={0};
	for(int i=1;i<=n;i++){
		L[i]=i-1; R[i]=i+1;
	}
	R[n]=0;
	for(int i=1;i<=n;i++){
		int now=num[i];
		L[0]=R[0]=0;
		int l1=L[now],r1=R[now],r2=R[R[now]];
		res+=pf(p[l1]-q[now])+pf(p[now]-r[r1])+pf(p[r1]-s[r2]);
		L[R[now]]=L[now];
		R[L[now]]=R[now];
		L[now]=R[now]=0;
	}
	return res;
}
double const T=1e7,cold=0.997;
int ans;
inline void SA(){
	for(int i=1;i<=n;i++) num[i]=rem[i];
	double tem=T;
	int tans=-1e16;
	while(tem>1e-16){
		tem*=cold;
		int x=rand()%n+1,y=rand()%n+1;
		swap(num[x],num[y]);
		tans=suan();
		if(tans>ans){
			ans=tans;
			for(int i=1;i<=n;i++) rem[i]=num[i];
		}
		else if(exp(-(ans-tans)*1.0/tem)*RAND_MAX>rand()){
			continue;
		}
		else swap(num[x],num[y]);
	}
	return ;
}

signed main(){
//	freopen("landmine.in","r",stdin);
//	freopen("landmine.out","w",stdout);
//	double a=clock();
	srand(19260817);
	rd(n);
	for(int i=1;i<=n;i++){
		rd(p[i]);
	}
	for(int i=1;i<=n;i++){
		rd(q[i]);
	}
	for(int i=1;i<=n;i++){
		rd(r[i]);
	}
	for(int i=1;i<=n;i++){
		rd(s[i]);
	}
	ans=-1e16;
	for(int i=1;i<=n;i++) rem[i]=i;
	for(int i=1;i<=10;i++){
		SA();
	}
//	double b=clock();
	out(ans);
//	printf("\nAC %.2lfms\n",b-a); 
	return 0;
}
2023/10/31 21:40
加载中...