记录编号	248623	评测结果	AAAAAAAA
题目名称	[Ural 1143] 青蛙的烦恼	最终得分	100
用户昵称	洛克索耶夫	是否通过	通过
代码语言	C++	运行时间	0.015 s
提交时间	2016-04-10 17:13:51	内存使用	0.39 MiB

#include<cstdio>
#include<cstring>
#include<cmath>

double dist(double x1, double y1, double x2, double y2)
{
	return sqrt((x2-x1)*(x2-x1)+(y2-y1)*(y2-y1));
}

double GetMin(double a, double b)
{
	return a<b?a:b;
}

double f[65][65][2]={0},dis[65][65]={0};
//因为是凸多边形,所以只能走相邻的未走的点才可能最短,才有相邻区间
//在[i,j]区间上,若在i,则能跳到i-1或j,在j同理 
//f[s][L][0]:从s出发,遍历s到s+L-1的最短距离 
//f[s][L][1]:从s+L-1出发遍历s到s+L-1的最短距离
//逆向思维,可以从任何地方跳,最后停在1号上,长度为x的区间可以由长度为x-1的区间推过来 

int main()
{
	freopen("frogpuzzle.in","r",stdin);
	freopen("frogpuzzle.out","w",stdout);
	int n;scanf("%d",&n);
	double x[65]={0},y[65]={0};
	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]=dis[j][i]=dist(x[i],y[i],x[j],y[j]);
		
	for(int l=2;l<=n;l++){//长度 
		for(int s=1;s+l<=n+1;s++){//起点
			int end=s+l-1;
			f[s][end][0]=GetMin(f[s][end-1][0]+dis[end-1][end],f[s][end-1][1]+dis[s][end]);
			//是从s+1还是从end 
			f[s][end][1]=GetMin(f[s+1][end][0]+dis[s][end],f[s+1][end][1]+dis[s][s+1]);
			//是到s还是到s+1,语句好长 
		} 
	}
	
	printf("%.3lf\n",f[1][n][1]);//这是最初,也是最终(逆向)
	return 0;
	
}