这道题居然可以O(n^2)解决, 让我太吃惊了!!!

鄙人见识浅薄, 这其实是一个经典问题: bitonic tour.

它的定义是:

从最左点走到最右点在走回来, 不重复经过点, 最小需要多少路程.

在最左点走到最右点的过程中, 只走到比当前点x坐标大的点, 反之同理. (在该题中, 没有两个点x坐标重复)

要得出\(O(n^2)\)的DP算法, 需要几步转化:

首先, 计算从左到右再回来的路径长度很麻烦(因为这样回来时要标记所有走过的点, 状态\(2^n\)), 不可行.

可以看成有两个人从最左点出发, 经过不同的路径, 最后都走到了最右点.

然后, 为了防止集合的标记, 我们定义以下状态:

\[ f(i, j) 表示 1... \max(i, j)都经过,第一个人到达i, 第二个人到达j的最短路长度.\\ 不妨设i>j.(请思考) \]

这样我们就无需标记经过的点了.

因为每次每个人都在向右走, 所以只要讨论一下是那个人走到了\(i+1\)就可以了.

这就是状态转移方程:

f[i+1][i] = min(f[i+1][i], f[i][j] + dist(j, i+1));            f[i+1][j] = min(f[i+1][j], f[i][j] + dist(i, i+1));

其实, "向右走" 就是一个天然的"序". 这就可以让该dp满足"无后效性"原则

这也就是TSP不能用这种方法的原因.

为何我们不会漏掉可能的情况?

思考一下, 是不是每一条走完{1..n}的路线都存在一个走完{1..i}(i<n)的子路线? 所以不会漏.

code

#include
    
     using namespace std;typedef long long ll;#define rep(_i, _st, _ed) for(int _i = (_st); _i <= (_ed); ++_i)#define per(_i, _ed, _st) for(int _i = (_ed); _i >= (_st); --_i)inline int read(){int ans = 0, f = 1; char c = getchar();while(c < '0' || c > '9') f = (c == '-') ? -1 : f, c = getchar();while('0' <= c && c <= '9') ans = ans*10 + c - '0', c = getchar();return ans;}const int maxn = 1005;double f[maxn][maxn];struct poi{    double x, y;    bool operator < (const poi &rhs) const{        return x < rhs.x;    }}p[maxn];int n;#define sqr(_x) ((_x)*(_x))double dist(int a, int b){    return sqrt(sqr(p[a].x-p[b].x) + sqr(p[a].y - p[b].y));}signed main(){    while(cin >> n) {        rep(i, 1, n) cin >> p[i].x >> p[i].y;        if(n == 1) {            puts("0.00");             continue;        }        sort(p+1, p+n+1);        rep(i, 1, n) rep(j, 1, n) f[i][j] = 1e10;                //i > j        f[2][1] = dist(1, 2);        rep(i, 2, n) rep(j, 1, i-1){            f[i+1][i] = min(f[i+1][i], f[i][j] + dist(j, i+1));            f[i+1][j] = min(f[i+1][j], f[i][j] + dist(i, i+1));        }        printf("%.2f\n", f[n][n-1] + dist(n, n-1));    }    return 0;}