记录编号	185277	评测结果	AAAAAAAA
题目名称	1510.[Ural 1143] 青蛙的烦恼	最终得分	100
用户昵称	mikumikumi	是否通过	通过
代码语言	C++	运行时间	0.011 s
提交时间	2015-09-05 15:38:38	内存使用	0.39 MiB

#include<cstdio>
#include<cmath>
#include<iostream>
#include<cstring>
#include<iomanip>
using namespace std;
int N;
double x[70],y[70];
double f[70][70][2]={0};
double dist(int a,int b)
{
	a=(a-1)%N+1,b=(b-1)%N+1;
	return sqrt((x[a]-x[b])*(x[a]-x[b])+(y[a]-y[b])*(y[a]-y[b]));
}
double DP(int i,int L,bool t)
{
	if(L==1) return 0.0;
	if(f[i][L][t]) return f[i][L][t];
	if(!t) f[i][L][t]=min(dist(i,i+1)+DP(i+1,L-1,0),dist(i+L-1,i)+DP(i+1,L-1,1));
	else f[i][L][t]=min(dist(i+L-1,i+L-2)+DP(i,L-1,1),dist(i+L-1,i)+DP(i,L-1,0));
	return f[i][L][t];
}
int main()
{
	freopen("frogpuzzle.in","r",stdin);
	freopen("frogpuzzle.out","w",stdout);
	scanf("%d",&N);
	for(int i=1;i<=N;i++)
		scanf("%lf%lf",&x[i],&y[i]);
	double ans=DP(1,N,0);
	printf("%.3lf",ans);
	return 0;
}