题目链接戳这里
太菜了..觉得这题好难...
大意是有n个按x坐标递增顺序给出的一些点，如何从最左点走到最右点，再从最右点走到最左点，路径总长度最短。要求除最左和最右外每个点恰好经过一次。
紫书的思路我这整理一下:
“从左到右再回来”思考不方便，改成：2人同时从最左出发，沿不同的路径走，最后都走到最右点，且除起点和终点外每个点恰好被1人经过。用d(i,j)表示第1个人走到i，第2个人走到j，还需走多长的距离。
但是这样很难保证2人不会走相同的点。比如计算状态d(i,j)，能不能让i走到i+1呢？不确定。说明这种状态定义不好。改用d(i,j)表示从1到max(i,j)的点都走过了，现在的位置是i和j，还需要走多长距离。
- 可以发现d(i,j)=d(j,i)，可以规定i>j。①
那么下一步可以走的点有i+1,i+2...如果走了i+2，情况是走过了1~i和i+2，i+1没走过，无法用d来表示状态，于是规定下一步不管是谁，总是走i+1.这里有个关键的地方：上述规定不会导致漏解，因为第1人若是直接走到i+2，再也无法走到i+1，只能靠第2人走到i+1。反正第2人都要走到i+1，不如当前就直接让第2人走到i+1的情况来看看。
- 所以，现在的情况就是：对于d(i,j) 下一步只有两种转移决策，要么是i走到i+1，要么是j走到 i+1;
d(i,j)只能转移到d(i＋1,j)和d(i＋1,i)， 第1个d代表第1人从i走到i+1，第2个d表示j走到i+1，即d(i,i+1)，但是由于①处的规定，因d(i,i+1)=d(i+1,i)，写作d(i+1,i)
到这儿，麻烦的就是边界条件了：d(n-1,j)=dist(n-1,n)+dist(j,n)，其中dist(a,b)表示点a和点b的距离。即只剩最后一个点(编号n)没走了，那么还剩多少路要走？2人到最后个点的距离之和便是了。
解是什么?
是dist(1,2)+d(2,1)，那为什么不写d(1,1)算了?别忘了规定①要求i>j喔.所以往前推一步。第一步定是有人到第二点，解为dist(1,2) 加从这种情况开始的所需距离..
代码:
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define mst(a,b) memset(a,b,sizeof(a))
#define rep(i,a,b) for(ll i=(a);i<(b);++i)
#define rrep(i,a,b) for(ll i=(b-1);i>=a;--i)
const int inf = 0x3f3f3f3f, maxN = 50 + 5;
int N, M;
double x[maxN], y[maxN], dist[maxN][maxN], d[maxN][maxN];
int main() {
// freopen("data.in", "r", stdin);
while (~scanf("%d", &N)) {
rep(i, 1, N + 1)
scanf("%lf %lf", &x[i], &y[i]);
rep(i, 1, N + 1)
rep(j, 1, N + 1)
dist[i][j] = sqrt(pow((x[i] - x[j]), 2)
+ pow((y[i] - y[j]), 2));
rrep(i, 2, N) {
rep(j, 1, i) {
if (i == N - 1)
d[i][j] = dist[i][N] + dist[j][N];
else
d[i][j] = min(dist[i][i + 1] + d[i + 1][j],
dist[j][i + 1] + d[i + 1][i]);
}
}
printf("%.2lf\n", dist[1][2] + d[2][1]);
}
return 0;
}
这里放张网友的心声..扎铁
网友评论