感觉很强的双调dp问题，不会做，看了解题报告才写的，感觉这题做法比较不错
说的是你从左边一个点走到右边一个点再走回来，要把途中的n-2个点走完，问最短路。
做法是假想两个人从左往右走，一起走到右边那个点的总路径，为了方便，不妨设前面那个人走到i，后一个
走到了j，用dp[i][j]表示这种状态的最短路，然后自底而上刷表，如果下一步是前一个走到i+1，更新就是dp[i+1][j]=min(dp[i+1][j],dp[i][j]+dis(i,i+1)),是后一个就是dp[i+1][i]=min(dp[i+1][i],dp[i][j]+dis(j,i+1)),然后就乱搞就行了。
#include<cstdio>
#include<cmath>
const double INF=9999999;
int n;
int x[101];
int y[101];
double dp[101][101];
double dis(int i,int j)
{
return sqrt((x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]));
}
double min(double a,double b)
{
return a<b?a:b;
}
int main()
{
while(1==scanf("%d",&n))
{
for(int i=1;i<=n;i++)
scanf("%d%d",&x[i],&y[i]);
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
dp[i][j]=INF;
dp[1][1]=0;
for(int i=1;i<=n;i++)
for(int j=1;j<=i;j++)
{
dp[i+1][j]=min(dp[i+1][j],dp[i][j]+dis(i,i+1));
dp[i+1][i]=min(dp[i+1][i],dp[i][j]+dis(j,i+1));
}
double ans=INF;
for(int j=1;j<n;j++)
if(ans>dp[n][j]+dis(j,n))
ans=dp[n][j]+dis(j,n);
printf("%.2f\n",ans);
}
return 0;
}