记录编号	86908	评测结果	AAAAAAAA
题目名称	[Ural 1143] 青蛙的烦恼	最终得分	100
用户昵称	cstdio	是否通过	通过
代码语言	C++	运行时间	0.004 s
提交时间	2014-01-28 20:31:12	内存使用	17.84 MiB

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<iomanip>
#include<queue>
#include<deque>
#include<set>
using namespace std;
const int SIZEN=1010;
int N;
double x[SIZEN]={0},y[SIZEN]={0};
double dist(int a,int b){
	if(a>N) a-=N;if(b>N) b-=N;
	return sqrt((x[a]-x[b])*(x[a]-x[b])+(y[a]-y[b])*(y[a]-y[b]));
}
double f[SIZEN][SIZEN][2]={0};
bool visit[SIZEN][SIZEN][2]={0};
double DP(int i,int L,int type){
	if(visit[i][L][type]) return f[i][L][type];
	visit[i][L][type]=true;
	if(L==1){
		f[i][L][type]=0;
		return 0;
	}
	if(!type) f[i][L][type]=min(dist(i,i+1)+DP(i+1,L-1,0),dist(i,i+L-1)+DP(i+1,L-1,1));
	else f[i][L][type]=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][type];
}
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]);
	//下面注释里是URAL上题目的代码
	/*double ans=1e20;
	for(int i=1;i<=N;i++) ans=min(ans,DP(i,N,0));
	printf("%.3lf",ans);*/
	printf("%.3lf",DP(1,N,0));
	return 0;
}