题意：平面上有n个点，所有点的x坐标均不同，两点之间的花费为两点之间的欧几里得距离，从最左面出发，到最右面返回
所有点除最左和最右路过两次，其他的路过一次，输出最小花费
分析：按照题意无法定义路过点的状态，把路径理解为两个人同时从最左出发，到达最右点，中间的点只能一个人走且只能一次，这样就可以用(i,j)表示两个人分别在点i和点j的，但是无法表示哪个点走没走过
强制规定i>j，j以前的点都走过了，这样就可以表示出走过点的状态，那么(i,j)只能向(i+1,j)和(i+1,i)转移
我用dp[i][j]表示一个人走到(i,j)这个状态的最小花费
#include<bits/stdc++.h> using namespace std; const int maxn=1e3+5; const double INF=0x3f3f3f3f; double dp[maxn][maxn],x[maxn],y[maxn]; double dis(int i,int j){ double dx=x[i]-x[j];dx*=dx; double dy=y[i]-y[j];dy*=dy; return sqrt(dx+dy); } int main(){ int n; while(~scanf("%d",&n)){ for(int i=1;i<=n;i++) scanf("%lf%lf",x+i,y+i); memset(dp,0,sizeof(dp)); dp[2][1]=dis(2,1); for(int i=3;i<=n;i++){ dp[i][i-1]=INF; for(int j=1;j<i-1;j++){ dp[i][j]=dp[i-1][j]+dis(i-1,i); dp[i][i-1]=min(dp[i][i-1],dp[i-1][j]+dis(j,i)); } } //答案就是min(dp[n][j]+dis(j,n)) double ans=INF; for(int i=1;i<n;i++) ans=min(ans,dp[n][i]+dis(n,i)); printf("%.2f\n",ans); } return 0; }
原文：http://www.cnblogs.com/jihe/p/5224965.html
