记录编号	248504	评测结果	AAAAAAAA
题目名称	[Ural 1143] 青蛙的烦恼	最终得分	100
用户昵称	_Itachi	是否通过	通过
代码语言	C++	运行时间	0.000 s
提交时间	2016-04-10 16:00:15	内存使用	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]);
		//f[i][j][0]代表从i到j；f[i][j][1]代表从j到i 
	}
	printf("%.3lf",f[1][n][1]);
	//必须确定一个端点为1，如果是 f[1][n][0]可能不是从1开始的，但 f[1][n][1]一定在1结束，可以倒过来，成为从1开始 
}