蓝桥杯 算法提高 ADV-277 The Islands(记录转移的简单动态规划)
程序员文章站
2022-07-15 12:28:44
...
题目大意:
二维平面上有n个点,每个点的坐标是整数,其中有两个特殊点A和B,现在把所有的点按照x坐标从小到大排序,要求一条从起点S到终点T再回到S的最短路径,要求每个点都要经过一次,并且在从S到T的过程中x坐标只能单增,从T回到S过程中x坐标只能单减。A点和B点要分别在去和回来的路上。要计算出最短路径长度,并输出路径。
思路:
假设节点从 号点到 号点 坐标依次增加。问题就等价于从 号点到 号点找到两条没有公共节点的路径,两个路径分别经过 点和 点,求两条路径长度的和最短。
设 表示从 号点第一条路径到 号点,第二条路径到 号点的两条路径的最短距离和。
那么对于 ,如果 ,那么下一个要决策的点就是 号点,这个点可以有两种方式,第一种是放到第一条路径上,那么 就转移到了 上;第二种是放到第二条路径上,那么就转移到了 状态上。如果 ,那么下一个要决策的点就是 号点,这个点也可以有两种方式,第一种是放到第一条路径上,那么 就转移到了 上面;如果是放到第二条路径上,那么就是转移到 状态上。
下面只要依次枚举每个状态,然后向后进行转移就可以了,这里注意对于 节点和 节点一定要设计转移,我们不妨假设 点一定在第一条路径上, 点一定在第二条路径上,这样就可以在转移之前先进行一个判断,就可以保证最后的答案一定是 和 在不同的路径上。此外转移的时候用 数组记一下上一个状态就可以从最后的状态一点点回溯会初始状态,也就知道了两个最短的路径的形式。
代码:
/*
2019-12-26 17:34:11
from xcx
个人博客地址:https://blog.csdn.net/qq_36306833
欢迎交流学习
*/
#include<bits/stdc++.h>
using namespace std;
const int maxn = 104;
struct point{
int x, y;
point(){}
point(int xx, int yy){
this->x = xx;
this->y = yy;
}
}a[maxn],pre[maxn][maxn];
int inline p2(int x){return x*x;}
inline double dis(point a, point b){
return sqrt(p2(a.x- b.x) + p2(a.y- b.y));
}
int n, m1, m2;
double dp[maxn][maxn];
bool vis[maxn][maxn];
int main(){
int cas = 1;
while(scanf("%d%d%d",&n,&m1,&m2)!=EOF){
if(n==0 && m1==0 && m2==0){
break;
}
m1++, m2++;
for(int i=1;i<=n;i++){
scanf("%d%d",&a[i].x, &a[i].y);
}
for(int i=0;i<=n;i++){
for(int j=0;j<=n;j++){
vis[i][j] = false;
dp[i][j] = 1e10;
}
}
dp[1][1] = 0;
for(int i=1;i<n;i++){
for(int j=1;j<n;j++){
if(i!=1 && i == j)continue;
if(i >= j){ // i+1的去哪
// dp[i][j] -> dp[i+1][j] = dp[i][j]+dis(i,i+1) dp[i][i+1] = dp[i][j]+dis(j,i+1)
if(i+1!=m2 && (vis[i+1][j] == false || dp[i+1][j] > dp[i][j] + dis(a[i], a[i+1]))){
pre[i+1][j] = point(i, j);
vis[i+1][j] = true;
dp[i+1][j] = dp[i][j] + dis(a[i], a[i+1]);
// printf("%d %d -> %d %d (1)\n",i,j,i+1,j);
}
if(i+1!=m1 && (vis[i][i+1] == false || dp[i][i+1] > dp[i][j] + dis(a[j], a[i+1]))){
pre[i][i+1] = point(i, j);
vis[i][i+1] = true;
dp[i][i+1] = dp[i][j] + dis(a[j], a[i+1]);
// printf("%d %d -> %d %d (2)\n",i,j,i,i+1);
}
}
if(i <= j){ // j+1的去哪
// dp[i][j] -> dp[i][j+1] = dp[i][j]+dis(j,j+1) dp[j+1][j] = dp[i][j]+dis(i,j+1)
if(j+1!=m1 && (vis[i][j+1] == false || dp[i][j+1] > dp[i][j] + dis(a[j], a[j+1]))){
pre[i][j+1] = point(i, j);
vis[i][j+1] = true;
dp[i][j+1] = dp[i][j] + dis(a[j], a[j+1]);
// printf("%d %d -> %d %d (3)\n",i,j,i,j+1);
}
if(j+1!=m2 && (vis[j+1][j] == false || dp[j+1][j] > dp[i][j] + dis(a[i], a[j+1]))){
pre[j+1][j] = point(i, j);
vis[j+1][j] = true;
dp[j+1][j] = dp[i][j] + dis(a[i], a[j+1]);
// printf("%d %d -> %d %d (4)\n",i,j,j+1,j);
}
}
}
}
/*for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
printf("dp[%d][%d] = %15.2f ",i,j,dp[i][j]);
}
printf("\n");
}
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
printf("pre[%d][%d] = (%d, %d) ",i,j,pre[i][j].x, pre[i][j].y);
}
printf("\n");
}*/
double ans = 1e20;
int posx = -1, posy = n;
for(int i=1;i<=n;i++){
if(i == m2)continue;
if(ans > dp[i][n]+ dis(a[i], a[n])){
ans = dp[i][n]+ dis(a[i], a[n]);
posx = i;
}
}
vector<int> way1, way2;
while(posx != 0 && posy != 0){
//printf("%d %d ->",posx,posy);
if(pre[posx][posy].x != posx){
way1.push_back(posx);
posx = pre[posx][posy].x;
}
else{
way2.push_back(posy);
posy = pre[posx][posy].y;
}
}
vector<int> xcx;
printf("Case %d: %.2f\n", cas++, ans);
for(int i=way1.size()-1;i>=0;i--){
xcx.push_back(way1[i]-1);
}
for(int i=0;i<way2.size();i++){
xcx.push_back(way2[i]-1);
}
xcx.push_back(0);
if(xcx[1] != 1){
reverse(xcx.begin(), xcx.end());
}
for(int i=0;i<xcx.size();i++){
if(i!=0){
printf(" ");
}
printf("%d",xcx[i]);
}
printf("\n");
}
return 0;
}