P1523 旅行商简化版

简化题意：

给定 \(n\) 个点，要求从最左端的点到最右端的点之间寻找两条互不重复的路径，两条路径经过所有点，且路径长度最小。输出最短路径长度。

思路：

动态规划。

应该也算比较套路了。设想有两个人同时从最左端的点开始走，设 \(f_{i, j}\) 表示第一个人走到了 \(i\) 点，第二个人走到了 \(j\) 点。为了简化问题，我们假设 \(i < j\)，且 \(1 \sim j\) 中所有的点都已经被走过了。接下来，我们考虑 \(j + 1\) 号点会被谁走。

1. \(j\) （也就是第二个人） 走了 \(j + 1\) 号点。这样显然是可以的。状态转移方程为 f[i][j + 1] = min(f[i][j + 1], f[i][j] + dist(j, j + 1));

2. \(i\) （也就是第一个人） 后来居上，直接走到了 \(j + 1\) 号点。这样我们的第一个和第二个人就要对调一下了。因为我们定义前后，是根据他们目前所在点横坐标的大小。这样直接对调并不影响结果。状态转移 f[j][j + 1] = min(f[j][j + 1], f[i][j] + dist(i, j + 1));

代码示例：

// 缺省源没有去掉，大家凑付看看吧
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
#define x first
#define y second
#define rep(i, a, b) for (int i = (a); i <= (b); i ++ )
#define rop(i, a, b) for (int i = (a); i < (b); i ++ )

using namespace std;

using PDD = pair<double, double>;

const int N = 1010;
double f[N][N];
int n; PDD p[N];

double dist(int a, int b) {
	double dx = p[a].x - p[b].x;
	double dy = p[a].y - p[b].y;
	return sqrt(dx * dx + dy * dy);
}

int main() {
	scanf("%d", &n);
	rep(i, 1, n)
		scanf("%lf%lf", &p[i].x, &p[i].y);
	sort(p + 1, p + n + 1); // 不要忘了按照横坐标排序，确保是从西向东走
	
	rep(i, 1, n) rep(j, i + 1, n)
		f[i][j] = 1145141919810.00 * 20221224.00;
	
	f[1][2] = dist(1, 2);
	rep(i, 1, n) rep(j, i + 1, n)
		f[i][j + 1] = min(f[i][j + 1], f[i][j] + dist(j, j + 1)),
		f[j][j + 1] = min(f[j][j + 1], f[i][j] + dist(i, j + 1));
	double res = 1145141919810.00 * 20221224.00;
	rop(i, 1, n) res = min(res, f[i][n] + dist(i, n));
	printf("%.2lf", res);
	return 0;
}