新的奇巧淫技

原题传送门

众所周知，模拟退火是一种很强大的算法，DP很强，但我模拟退火也不虚，很多题你如果不会的话基本可以拿来水很多分。比如这道题，我用模拟退火可以轻松水过（虽然我是足足交了两页才过）但是没有什么大问题，如果模拟退火还不会，建议先看你谷日报学习一下。剩下的主要就是一些细节，看代码。

#include <bits/stdc++.h>

using namespace std;

#define gc getchar()

#define re register

double st=clock();

int n,tot,ans,x,y;

int I[1000000+10],E[1000000+10];

struct node{

	int IQ,EQ;

}a[1000000+10];//定义结构体，方便random_shuffle

inline int read(){

	int r=0,l=1;char ch=gc;

	while(!isdigit(ch)){if(ch=='-')l=-1;ch=gc;}

	while(isdigit(ch)){r=(r<<3)+(r<<1)+ch-'0';ch=gc;}

	return r*l;

}

inline void add(int x,int y){

	if(x<0&&y<0)return;//如果两个都是0,都答案没有任何贡献，直接pass

	if(x>=0&&y>=0)

		return a[++tot]=(node){x,y},void();//如果两个都>0,那么最优解一定会有它，直接加进去即可

	if((x<0&&y>0&&abs(x)-y>=rand())||(x>0&&y<0&&abs(y)-x>=rand()))return;//如果两个值是一正一负相差太大可以pass，但一定要注意是>rand()，这样会有一定概率接受这个解，至于为什么，留给读者思考

	if(x+y<0)if(exp(-(x+y))>(double)rand()/(double)RAND_MAX)return;//如果两个值相加为0,对答案会有负贡献，但仍要有一定几率接受，好像和上面判重了，因为本人太菜，不知道去掉对不对，所以就写上了～

	a[++tot]=(node){x,y};

}

inline void solve(){

	tot=0;for(re int i=1;i<=n;++i)add(I[i],E[i]);//初始化，重新选取合适牛

	random_shuffle(a+1,a+tot+1);//打乱重排

	x=0,y=0;

	for(re int i=1;i<=tot;++i){

		x+=a[i].IQ;y+=a[i].EQ;

		if(x<=0&&y<=0)//到此为止，答案已经不合法

			if(exp(ans-x-y)>(double)rand()/(double)RAND_MAX)return;//运用模拟退火思想，虽然已经不合法，但考虑后面可能有解加上后就合法，所以有一定概率接受这个解并继续。这也是模拟退火算法的优势

		if(x>0&&y>0)ans=max(ans,x+y);//合法的话，更新答案

	}

}

int main(){

	srand(time(NULL));

	n=read();

	for(re int i=1;i<=n;++i)I[i]=read(),E[i]=read();//存取各头牛的IQ和EQ，因为上方add时会有删除，因为是随机删除，可能会造成第一次就把最优解中的一头牛删除，然后就挂了，上面我的64分就是这样错的

	int crl=15000;

	while(crl--)solve();

	printf("%d\n",ans);

	return 0;

}

巴特西

P2340 [USACO03FALL]Cow Exhibition G题解

新的奇巧淫技

random_shuffle大法好

最新文章

热门文章