洛谷 P1523 旅行商简化版【线性dp+npc问题简化版】

原题链接：https://www.luogu.com.cn/problem/P1523

题目背景

欧几里德旅行商(Euclidean Traveling Salesman)问题也就是货郎担问题一直是困扰全世界数学家、计算机学家的著名问题。现有的算法都没有办法在确定型机器上在多项式时间内求出最优解，但是有办法在多项式时间内求出一个较优解。

为了简化问题，而且保证能在多项式时间内求出最优解，J.L.Bentley 提出了一种叫做 bitonic tour 的哈密尔顿环游。它的要求是任意两点 (a,b)?之间的相互到达的代价 dist(a,b)=dist(b,a)?且任意两点之间可以相互到达，并且环游的路线只能是从最西端单向到最东端，再单项返回最西端，并且是一个哈密尔顿回路。

题目描述

本题为著名的 NPC 难题的简化版本。

现在笛卡尔平面上有 (n≤1000)?个点，每个点的坐标为(x,y)，<x,y<，且为整数），任意两点之间相互到达的代价为这两点的欧几里德距离，现要你编程求出最短 bitonic tour。

输入格式

第一行一个整数?n。

接下来?n?行，每行两个整数 x,y，表示某个点的坐标。

输入中保证没有重复的两点，保证最西端和最东端都只有一个点。

输出格式

一行，即最短回路的长度，保留?2位小数。

输入输出样例

输入 #1

7
0 6
1 0
2 3
5 4
6 1
7 5
8 2

输出 #1

25.58

说明/提示

题目来源

《算法导论（第二版）》 15-1

解题思路：

这个题目是npc问题的简化版，也就是旅行商问题的简化版，

简化之后很像：P1006 [NOIP2008 提高组] 传纸条

这俩个题目的解题思想非常的像，但是又不完全相同，因为传纸条这个题目走的过程中间俩个人是允许走同一个点的，只是效益只计算一次，但是这个题目俩个人不允许走同一个点，首先我们利用类似传纸条这题的思想对题目进行类似转换，对于本题我们同样可以将来回走，变为俩个人一起从西边的点走到东边的点，这样就将原问题转换为了有俩个人从最西边的点都走到最东边的点，并且中间的每个点走且只走一次，这样我们就可以根据传纸条这题的思想来设计状态了，注意走的过程中由于不能走同样的点，所以走的过程中必然一个在前一个在后，我们还需要对于所有点按照横坐标从小到达排序。

状态定义

定义f[i][j]表示后面那个人走到i这个点，前面那个人走到j这个点，并且i<j，并且1~j之间的所有点都走过一次了的最短距离。

初始化

由于必须从西往东依次走过每一个点，我们最开始一定后面那个人在1号点，前面那个人在2号点，所以初始化为f[1][2]=d[1][2]

状态转移

当前i在后面,j在前面，1~j之间的所有点都已经走过了，接下来要走的点是j+1,那么存在俩种情况

(1)让j走到j+1,i暂时不动

(2)让i走到j+1,j暂时不动,会导致i走到j前面，为了保证前后性，我们交换i,j的位置

j走到j+1,i暂时不动

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

i走到j+1,j暂时不动，并且需要交换i，j位置，原本i变为j+1，j还是j，现在交换变为i变为j，j变为j+1,交换位置才能保证前面那个仍然在前面，后面那个也仍然在后面。

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

最终答案

最后一步一定是前面那个人已经到达了n号点，后面那个人可以在中间的任意一个点，后面那个人还没有到达终点，然后后面那个人走到n号点(终点)，所以答案就是所有的min(f[i][n]+d[i][n])(1<=i<n)

时间复杂度：第一维枚举后面那个人当前所在点，时间为O(n)，第二维枚举前面那个人当前所在点，时间为O(n)，最终时间复杂度为O(n^2)，n=1000，最终时间就是1e6，这个时间复杂度是肯定可以过的。

空间复杂度：俩个数组都是二维，空间复杂度为O(n^2)。

cpp代码如下：

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

using namespace std;

const int N = 1010;

int n;
struct points
{
    double x, y;
} a[N]; // 存储所有点的坐标
double f[N][N], d[N][N];

double get_distance(points u, points v) // 计算俩点之间的距离
{
    double dx = u.x - v.x, dy = u.y - v.y;
    return sqrt(dx * dx + dy * dy);
}
int main()
{
    cin >> n;
    for (int i = 1; i <= n; i++)
        scanf("%lf%lf", &a[i].x, &a[i].y);
    // 按照横坐标从小到达排序
    sort(a + 1, a + 1 + n, [&](points A, points B)
         { return A.x < B.x; });

    // 初始化距离数组d和dp数组f
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
        {
            d[i][j] = d[j][i] = get_distance(a[i], a[j]);
            f[i][j] = 1e30;
        }
    // 初始时走在后面的那个人在1号点，走在前面的那个人在2号点，由于必须是从习往东一次走每个点，所以最开始俩人必然在1,2号点
    f[1][2] = d[1][2];
    for (int i = 1; i < n; i++)
        for (int j = i + 1; j <= n; j++) // 前面那个人要在后面那个人前面，所以这里从i+1开始枚举
        {
            /*
                当前i在后面,j在前面，1~j之间的所有点都已经走过了，接下来要走的点是j+1,那么存在俩种情况
                (1)让j走到j+1,i暂时不动
                (2)让i走到j+1,j暂时不动
            */
            // j走到j+1,i暂时不动
            f[i][j + 1] = min(f[i][j + 1], f[i][j] + d[j][j + 1]);
            // i走到j+1,j暂时不动
            f[j][j + 1] = min(f[j][j + 1], f[i][j] + d[i][j + 1]);
        }
    /*
        最后一步一定是前面那个人已经到达了n号点，后面那个人可以在中间的任意一个点，后面那个人还没有到达终点，
        然后后面那个人走到n号点(终点)，所以答案就是所有的min(f[i][n]+d[i][n]) (1<=i<n)
    */
    double ans = 1e30;
    for (int i = 1; i < n; i++)
        ans = min(ans, f[i][n] + d[i][n]);
    printf("%.2lf\n", ans);
    return 0;
}