问题描述：


双调欧几里得旅行商问题是一个经典动态规划问题。《算法导论（第二版）》思考题15-1和北京大学OJ2677都出现了这个题目。

旅行商问题描述：平面上n个点，确定一条连接各点的最短闭合旅程。这个解的一般形式为NP的（在多项式时间内可以求出）

J.L. Bentley 建议通过只考虑双调旅程(bitonictour)来简化问题,这种旅程即为从最左点开始，严格地从左到右直至最右点，然后严格地从右到左直至出发点。下图(b)显示了同样的7个点的最短双调路线。在这种情况下，多项式的算法是可能的。事实上，存在确定的最优双调路线的O(n*n)时间的算法。



HDU-2224：

题目大意：

                    给你n个点，严格规定从从起始点1走到最右端n在从n返回1，并且所有点都只经过一次，求最短路径；

题目思路：

                 看别人的博客看了好久好久，然后自己一步一步去模拟，最后也算是理解了怎么来的，下面我就说下我对该算法的理解

首先考虑这个问题的子问题，我们定义dis[i][j]为从i到j的直线距离，定义dp[i][j]  （考虑i<=j）为从i出发走到起始点（递减）再返回

走到j（递增）的最短路程，所以我们知道dp[i][j]为从起始点1走到j的最短路程，所以dp[n][n]就是我们要求的答案!   然后我们来分析下状态转移

1:  i<j-1  :

                我们来考虑下dp[i][j]可以由什么得来，我们看下j-1这个点，因为i<j-1，所以我们可以知道最后一定是由j-1走到j的，所以我们

可以得到dp[i][j]=dp[i][j-1]+dis[j-1][j]

2:  i==j-1 ：

              我们再来考虑下j-1这个点，因为i=j-1所以就相当于i点，该点一定是从i点走到1- i-1中的一点，那么我们要找的是最短路程的哪一点，

所以我们可以遍历 {dp[k][i]+dis[k][j],1=<k<i}找一个最小的值，所以此时k点就是我们要找的点，所以 dp[i][j] = dp[k][i] +dis[k][j] 

 这里我们可以看成由j-i，先j-k再k-i，然后找一个最小路程


然后有了上面的分析就可以写代码了~~    可以当做模板哈~~~


AC代码：


#include<algorithm>
#include<iostream>
#include<cstdio>
#include<cmath>

#define db double

using namespace std;

const int maxn = 205;
const db inf = 1e9;

class TSP{
public:
    int n;
    db x[maxn],y[maxn],dis[maxn][maxn],dp[maxn][maxn];

    db cal(db x1,db x2,db y1,db y2){return sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));}

    void sove(){
        dp[1][2]=dis[1][2];
        for(int j=3;j<=n;j++){
            // i<j-1
            for(int i=1;i<=j-2;i++)dp[i][j]=dp[i][j-1]+dis[j-1][j];
            //i=j-1
            db Min=inf;
            for(int k=1;k<=j-2;k++)Min=min(Min,dp[k][j-1]+dis[k][j]);
            dp[j-1][j]=Min;
        }
        dp[n][n]=dp[n-1][n]+dis[n-1][n];
        printf("%.2lf\n",dp[n][n]);
    }

    int init(){
       if(scanf("%d",&n)==-1)return -1;
       for(int i=1;i<=n;i++)scanf("%lf%lf",&x[i],&y[i]);
       for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)dis[i][j]=cal(x[i],x[j],y[i],y[j]);
       sove();
    }

}tp;

int main()
{
    while(~tp.init());
    return 0;
}