目录
题目大意
样例解释
第一组样例解释
第二组样例解释
有注释的代码
没有注释的代码
题目大意
样例解释
（多组样例）
第一组样例解释
第二组样例解释
（没有注释的代码实际上很短 在后面）
有注释的代码
思路和心得都在代码里, 快去看看吧👇
(把代码复制到Dev-C++里 效果更佳)
(最后有不加注释的代码)
#include <iostream>
#include <cmath>
using namespace std;
const int N = 1005;
double x[N], y[N], dp[N][N];
double dist(int i, int j) {
return sqrt((x[i] - x[j]) * (x[i] - x[j]) + (y[i] - y[j]) * (y[i] - y[j]));
}
int main() {
int n;
while (cin >> n) {
for (int i = 1; i <= n; i ++)
cin >> x[i] >> y[i];
/*
****** 严重警告~这整块注释请仔细阅读!!! ******
↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓
这题如果考虑先往左走 再往右走 会很麻烦
不如 考虑成选两条从左往右的路 且包括所有的节点
dp(i, j) : 一个人走到i 另一个人走到j (1~max(i, j)都走过) 还需多少路程
易知 dp(i, j) = dp(j, i)
所以我们规定 i > j (这样更方便)
及dp(i, j) 1 ~ i 都已经走过了
那么 我们规定 只能走到 i + 1
所以要么 i 走到 i+1 ,要么 j 走到 i+1
dp(i, j) 就只能转到
1). dp(i + 1, j)
i =转到=> i + 1
2). dp(i, i + 1) 及 dp(i + 1, i)
j =转到=> i + 1 (因为这里j转到的 i+1 一定>i)
又细心的会问 :"这么暴力的规定 不会漏掉一些情况么"
好, 我们这里先举个例子
如果 要一个人走到 i+2 咋整
因为这样 i+1 就漏走了 只能另一个人走 i+1
那么 我们可以先让另一个人走到 i+1 这个人再走到 i+2 结果也不会影响
这样就不会丢失解
我们把边界设定一下
如果 一个人在 n-1 另一个人在 j
那么 只有将 j 走到 n, 再将 n-1 走到 n, 就有如下
dp(n-1, j) = dist(n-1 + n) + dist(j, n);
dist(i, j): 点 i 到点 j 的距离
现在分析完了, 正片开始!!!
*/
//初始化
for (int j = 1; j <= n; j ++)
dp[n - 1][j] = dist(n - 1, n) + dist(j, n);
for (int i = n - 2; i >= 1; i --) //倒推
for (int j = 1; j < i; j ++)
dp[i][j] = min(dp[i + 1][j] + dist(i, i + 1),
dp[i + 1][i] + dist(j, i + 1));
printf ("%.2lf\n", dp[2][1] + dist(1, 2));
}
return 0;
}没有注释的代码
#include <iostream>
#include <cmath>
using namespace std;
const int N = 1005;
double x[N], y[N], dp[N][N];
double dist(int i, int j) {
return sqrt((x[i] - x[j]) * (x[i] - x[j]) + (y[i] - y[j]) * (y[i] - y[j]));
}
int main() {
int n;
while (cin >> n) {
for (int i = 1; i <= n; i ++)
cin >> x[i] >> y[i];
for (int j = 1; j <= n; j ++)
dp[n - 1][j] = dist(n - 1, n) + dist(j, n);
for (int i = n - 2; i >= 1; i --)
for (int j = 1; j < i; j ++)
dp[i][j] = min(dp[i + 1][j] + dist(i, i + 1),
dp[i + 1][i] + dist(j, i + 1));
printf ("%.2lf\n", dp[2][1] + dist(1, 2));
}
return 0;
}题目传送门：旅行 Tour - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
制作不易，留个赞再走吧
