题目链接：点击打开链接
算是被简化了的旅行商问题，其实这道题就是算法导论的第15章的思考题15-3，又称为双调欧几里得旅行商问题。
算导里面给出了这个提示：【由左至右扫描，对巡游路线的两个部分分别维护可能的最优解】
于是便能够得到这道题的dp状态表示方法了。
我们假设其并不是从最左出发至最右再从最右往左走，而是从最左开始同时往右走两条路至最右。
于是便可以设dp[i][j]为，从最左边的点出发往一条路走到点i，再往另一条路走到点j的最短路径。
从左往右枚举最右的点p并且不断更新含有p的dp[i][j]即可。
总时间复杂度为O(n^2)。
题目中没有给出n的范围，不过亲测n应该在1000或以下。
代码如下：
#include<bits/stdc++.h> #define MAXN 4005 using namespace std; struct node { double x,y; double operator -(const node &a)const { return sqrt((x-a.x)*(x-a.x)+(y-a.y)*(y-a.y)); } }; node a[MAXN]; double dp[MAXN][MAXN]; bool vis[MAXN][MAXN]; int main() { int n; while(scanf("%d",&n)==1) { for(int i=0;i<n;i++) scanf("%lf%lf",&a[i].x,&a[i].y); dp[0][0]=0; memset(vis,0,sizeof(vis)); vis[0][0]=true; for(int i=0;i<n;i++) { for(int j=0;j<i;j++) { if(!vis[i][i]) { vis[i][i]=true; dp[i][i]=dp[i][j]+(a[i]-a[j]); } else dp[i][i]=min(dp[i][i],dp[i][j]+(a[i]-a[j])); dp[i][i]=min(dp[i][i],dp[j][i]+(a[i]-a[j])); } // for(int j=0;j<=i;j++) // printf("dp[%d][%d]=%lf\ndp[%d][%d]=%lf\n",i,j,dp[i][j],j,i,dp[j][i]); for(int j=0;j<=i;j++) { if(!vis[i+1][j]) { vis[i+1][j]=true; dp[i+1][j]=dp[i][j]+(a[i+1]-a[i]); } else dp[i+1][j]=min(dp[i+1][j],dp[i][j]+(a[i+1]-a[i])); if(!vis[i][i+1]) { vis[i][i+1]=true; dp[i][i+1]=dp[i][j]+(a[i+1]-a[j]); } else dp[i][i+1]=min(dp[i][i+1],dp[i][j]+(a[i+1]-a[j])); if(!vis[j][i+1]) { vis[j][i+1]=true; dp[j][i+1]=dp[j][i]+(a[i+1]-a[i]); } else dp[j][i+1]=min(dp[j][i+1],dp[j][i]+(a[i+1]-a[i])); if(!vis[i+1][i]) { vis[i+1][i]=true; dp[i+1][i]=dp[j][i]+(a[i+1]-a[j]); } else dp[i+1][i]=min(dp[i+1][i],dp[j][i]+(a[i+1]-a[j])); } } printf("%.2lf\n",dp[n-1][n-1]); } }