记录编号	248613	评测结果	AAAAAAAA
题目名称	[Ural 1143] 青蛙的烦恼	最终得分	100
用户昵称	Hzoi_	是否通过	通过
代码语言	C++	运行时间	0.013 s
提交时间	2016-04-10 17:10:05	内存使用	0.41 MiB

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<ctime>
#include<cstdlib>
using namespace std;
double f[70][70][2],x[70],y[70],dis[70][70],t,temp=0,r;
bool vis[70][70][2]={{{0}}};
int n;
double min(double,double);
int main(){
#define COGS
#ifdef COGS
	freopen("frogpuzzle.in","r",stdin);
	freopen("frogpuzzle.out","w",stdout);
#endif
	srand(time(NULL));
	scanf("%d",&n);
	for(int i=1;i<=n;i++)scanf("%lf%lf",&x[i],&y[i]);
	for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)dis[i][j]=sqrt(pow(x[i]-x[j],2)+pow(y[i]-y[j],2));
	int a=rand()%n&1;
	if(a){//其中一种 
		for(int d=2;d<=n;d++)for(int j,i=1;i<=n-d+1;i++){
			j=i+d-1;
			f[i][j][1]=min(f[i+1][j][0]+dis[i][j],f[i+1][j][1]+dis[i][i+1]);
			f[i][j][0]=min(f[i][j-1][0]+dis[j-1][j],f[i][j-1][1]+dis[i][j]);
			//f[i][j][0]代表从i到j；f[i][j][1]代表从j到i
			//哎呦，不错哦，好好琢磨琢磨
		}
	}
	else{//另一种
		for(int d=2;d<=n;d++)for(int j,i=1;i<=n-d+1;i++){
			j=i+d-1;
			f[i][j][0]=min(f[i+1][j][0]+dis[i+1][i],f[i+1][j][1]+dis[i][j]);
			f[i][j][1]=min(f[i][j-1][0]+dis[i][j],f[i][j-1][1]+dis[j-1][j]); 
		}
		//状态定义不太一样，输出的也不同
	}
	//第二种有点问题，我哪知道咋回事
	printf("%.3lf",f[1][n][a]);
	return 0;
}
inline double min(double a,double b){
	if(a>b)return b;
	return a;
}