记录编号	248502	评测结果	AAAAAAAA
题目名称	1510.[Ural 1143] 青蛙的烦恼	最终得分	100
用户昵称	_Itachi	是否通过	通过
代码语言	C++	运行时间	0.000 s
提交时间	2016-04-10 15:55:53	内存使用	0.00 MiB

#include<cstdio>
#include<cstring>
#include<cmath>
#define fre freopen("frogpuzzle.in","r",stdin);freopen("frogpuzzle.out","w",stdout);
using namespace std;
double _rabit();
double x[61],y[61],dis[61][61],tot,f[61][61][2],xx=_rabit();
double _min(double a,double b){if(a>b)return b;return a;}
int main(){;}
double _rabit(){
	fre
	int n;scanf("%d",&n);
	memset(dis,0,sizeof(dis));
	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++)
	if(i!=j)
	if(dis[j][i]!=0)dis[i][j]=dis[j][i];
	else dis[i][j]=sqrt((x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]));
	
	for(int v=2;v<=n;v++)
	for(int j,i=1;i<=n-v+1;i++){
		j=i+v-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]);
	}
	tot=f[1][n][1];
	//if(f[1][n][1]<tot)tot=f[1][n][1];
	printf("%.3lf",tot);
}