「UVa 1347」Tour

发表于 | | 阅读次数:
字数统计: 757 字

Description

题目链接：UVa 1347

给定 $n$ 个点 $(x_i,y_i)$，求一条路径从最左边的点开始向右走到最右边的点，再向左走回到起点（必须严格向左向右），使得除了出发点每个点恰好经过一次。两点之间的距离为欧几里得距离。求最小路径长度，保留两位小数。

数据范围：$1\le n\le 1000$

Solution

直接考虑先向右再向左走不方便思考。我们可以把题目改为：两个人同时从最左边的点出发，沿着两条不同的路径走，最后都达到最右边的点。于是我们可以用 $f_{i,j}$ 表示两个人分别走到 $i,j$ 还需要还需要走多长距离。但是如何转移呢？这种方法显然无法记录每个点是否被访问过。因此这个状态定义不当，导致转移困难 QAQ

我们修改一下状态 $f_{i,j}$ 表示 $1\sim\max(i,j)$ 都访问过，且两个人当前在 $i$ 和 $j$，还需要走的路程，可得 $f_{i,j}=f_{j,i}$，因此我们强制 $i>j$。这样无论哪个人下一步只能走到标号比 $i$ 大的点。由于我们定义 $1\sim\max(i,j)$ 都访问过，所以下一步只允许一个人走到 $i+1$ 而不能到 $i+2,i+3,\cdots$，故 $f_{i,j}$ 只能转移到 $f_{i+1,j}$ 和 $f_{i+1,i}$（此处第二个人走到 $i+1$ 应该写成 $f_{i,i+1}$，但是根据定义只能写成 $f_{i+1,i}）$。

这样的转移是否会漏解呢？如果第一个人直接走到了 $i+2$，那么他再也无法到 $i+1$ 了，只能考第二个人到 $i+1$。那么我们直接让第二个人到 $i+1$ 即可，并不会漏解！

转移方程为：

边界是 $f_{n-1,j}=dist_{n-1,n}+dist_{j,n}$。因为第一步一定是某个人走到了第 $2$ 个点，故答案为 $f_{2,1}+dist_{1,2}$。

以上过程中，$dist_{a,b}$ 表示点 表示点 $a$ 和 和 b$ 之间的欧几里得距离。

时间复杂度：$O(n^2)$

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
 
#include <cstdio>
#include <cmath>
#include <algorithm>
#define FOR(i,a,b) for(int i=a;i<=b;++i)
#define REP(i,a,b) for(int i=a;i>=b;--i)
const int N=1005;
int n,x[N],y[N];
double dis[N][N],f[N][N];

double distance(int x1,int y1,int x2,int y2) {
    int xx=x1-x2,yy=y1-y2;
    return sqrt(xx*xx+yy*yy);
}
int main() {
    while(~scanf("%d",&n)) {
        FOR(i,1,n) scanf("%d%d",&x[i],&y[i]);
        FOR(i,1,n) FOR(j,1,n) dis[i][j]=distance(x[i],y[i],x[j],y[j]);
        REP(i,n-1,1) FOR(j,1,i-1) {
            if(i==n-1) f[n-1][j]=dis[n-1][n]+dis[j][n];
            else f[i][j]=std::min(f[i+1][j]+dis[i][i+1],f[i+1][i]+dis[j][i+1]);
        }
        printf("%.2lf\n",f[2][1]+dis[1][2]);
    }
    return 0;
}
0%