Chapter_9 DP : uva1347 tour (bitonic tour)

https://cn.vjudge.net/problem/UVA-1347

这道题居然可以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<bits/stdc++.h>
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,n) rep(j,n) f[i][j] = 1e10;
        
        //i > j
        f[2][1] = dist(1,2);

        rep(i,2,i-1){
            f[i+1][i] = min(f[i+1][i],i+1));
        }
        printf("%.2fn",f[n][n-1] + dist(n,n-1));
    }
    return 0;
}