植物大战僵尸这款游戏中，还有个特别有意思的赚钱方式——种花（能长金币的花）。
种出来的金币需要玩家点击才能得到，或者，玩家可以购买一只蜗牛来帮助捡金币。然而，蜗牛爬得慢是众所周知的。所以，场上有若干金币时，蜗牛总是喜欢以最少的行程来捡走所有的金币。
现在告诉你场上n个金币所在位置的坐标，以及蜗牛所在位置，让你求出蜗牛捡走所有金币的最小行程。
比较神奇，数据量是16，dfs可以过；随机化搜索，很稳定（所有的点都相同的时间）；
1 #include<iostream> 2 #include<cstdio> 3 #include<ctime> 4 #include<cstdlib> 5 #include<cmath> 6 using namespace std; 7 #define up(i,p,n) for(int i=p;i<=n;i++) 8 #define down(i,n,p) for(int i=n;i>=p;i--) 9 namespace OI{10const int maxn=20,inf=100000000;11int n,a[maxn][2],q[maxn];12double d[maxn][maxn];13void swa(int i,int j){14 for(;i<=j;i++,j--){15 swap(q[i],q[j]);16 }17}18double slove(){19 up(i,1,100){20 int x=rand()%n+1;21 int y=rand()%n+1;22 if(x==n)x=n-1;if(y==n)y=n-1;23 swap(q[x],q[y]);24 }25 up(i,1,n)up(j,i+1,n-1)26 if(d[q[i]][q[i+1]]+d[q[j-1]][q[j]]>d[q[i]][q[j-1]]+d[q[i+1]][q[j]])swa(i+1,j-1);27 double t=0;28 up(i,1,n-1)t+=d[q[i]][q[i+1]];29 return t;30}31int squ(int x){return x*x;}32void init(){33 srand(time(0));34 scanf("%d",&n);n++;35 up(i,1,n)scanf("%d%d",&a[i][0],&a[i][1]);36 up(i,1,n)up(j,1,n)37 d[i][j]=sqrt(1.0*squ(a[i][0]-a[j][0])+squ(a[j][1]-a[i][1]));38 //up(i,1,n)up(j,1,n)printf("%d %d %.2lf\n",i,j,d[i][j]);39 up(i,1,n)q[i]=i;40 double ans=(double)inf;41 up(i,1,50000){42 double t=slove();43 if(t<ans)ans=t;44 }45 printf("%.2lf\n",ans);46}47 }48 int main(){49//freopen("1.in","r",stdin);50//freopen("1.out","w",stdout);51OI::init();52return 0;53 }
View Code
如果觉得《种花小游戏 随机化搜索》对你有帮助，请点赞、收藏，并留下你的观点哦！
