By yusijia

Updated:

Contents
  1. 1. 题目大意：
  2. 2. 思路：
  • 参考：《算法竞赛入门经典》(白书)

题目大意：

　　给n(n<=1000)个点的坐标(按x递增,且各个点的坐标不同，都为正整数)，设计一条线路，从最左边的点出发，走到最右边的点然后返回，要求除了最左点和最右点之外每个点恰好经过一次，且路径总厂最短。两点的长度为他们的欧几里得距离。

思路：

  1. 定义d(i,j)表示1~max(i,j)全部走过，第一个人在i,第二个人在j，还需要走多长的距离。
  2. 然而这样似乎很难保证两个人不会走到相同的点，所以需要改下。因此，定义状态中i>j(这样不管哪个人，下一步只能到i+1,i+2,…这些点)，且状态d(i，j)
    只能转移到d(i+1,j)和d(i+1,i)
  • 注意：d(i+1,j)代表第一个人走到i+1，第二个人走到j，就是说第一个人向前走了一步。而d(i+1,i)代表第一个人走到i，第二个人走到i+1，就是说第二个人向前走了一步。(d(i,j)其实就等于d(j,i)，就是交换了下人而已,这里要把d(i,i+1)写成d(i+1,i)因为规定了状态是i>j的)。

  • 边界是d(n-1, j) = dist(n-1, n) + dist(j, n);

  • 至此，不得不佩服刘老师的解法。

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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63

#include<iostream>
#include<cmath>
#include<cstdio>
#include<algorithm>
using namespace std;

const int N = 1010;

struct point
{
    double x;
    double y;
};

point p[N];
double dp[N][N];
double dis[N][N];

int cmp(point a, point b)
{
    if(a.x < b.x)
        return 1;
    return 0;
}

double dist(int i, int j)
{
    if (dis[i][j] >= 0)//剪枝
        return dis[i][j];
    return dis[i][j] = sqrt((p[i].x - p[j].x)*(p[i].x - p[j].x) + (p[i].y - p[j].y)*(p[i].y - p[j].y));
}

double DP(int i, int j)
{
    if (dp[i][j] >= 0)//剪枝，记忆化搜索
        return dp[i][j];
    return dp[i][j] = min(DP(i + 1, j) + dist(i, i + 1), DP(i + 1, i)+dist(j,i+1));
}

int main()
{
    freopen("input.txt", "r", stdin);
    int n;
    while (scanf("%d", &n) != EOF){
        for(int i = 0; i < N; i++){
            for(int j = 0; j < N; j++){
                dp[i][j] = -1;
                dis[i][j] = -1;
            }
        }
        for(int i = 0; i < n; i++)
            scanf("%lf%lf", &p[i].x, &p[i].y);

        sort(p, p + n, cmp);

        for (int j = 0; j < n; j++)
            dp[n - 2][j] = dist(n - 2, n - 1) + dist(j, n - 1);//初始化

        printf("%.2lf\n", DP(0, 0));
    }
    return 0;
}
Contents
  1. 1. 题目大意：
  2. 2. 思路：