HDU 2224 The shortest path
属于动态规划。TSP(旅行商)问题的简化版本,双调旅行商问题。时间复杂度O(n^2)
。
可以参考这个。
给你平面上n
个点的坐标,这些点的x
坐标依次增大,让你找一条满足这样的性质的最短的路:从1
出发,沿着x
增大的方向走到n
,再沿着x
减小的方向走回1
,在这途中除了1
以外的每个点都要访问一次且仅一次。
这道题完全就是动态规划,只是背景好像最短路一样,其实和最短路算法没任何关系。
我们可以这样想,其实就是找两条1->n
的路,这两条路满足除了1
和n
之外都不重叠而且每个点都访问过(为什么能改变方向呢?想一想这道题的边权就是两点间的距离,是无向的)。
所以,dp[j][i] (j<i)
表示一条路从1
到j
点,一条路从1
到i
点,这样的两条路的和的最小值(这两条路是互相纠缠的,所以不能说最小值的和)(重要!这两条路满足两条性质:1. 除了1
之外不重叠;2. 所有小于等于i
的点都已被这两条路访问)。第二条性质非常非常重要!
dp[j][i]
和dp[i][j]
是等价的,我们只需要保持j<i
,仅在最后我们才需要让j=i
,以得到dp[n][n]
的值。
好了,我直接把代码弄上来,不要问我转移方程为什么是这样或者这样为什么对,我不知道,我只能说明不这样为什么错。
先看1
处,现在j
和i
至少差了两段(中间至少差了一个点),若是按2
处的写法来写,则违背了性质2
,因为小于j
的路直接到了i
,这两条路都到不了i
和j
中间差的那个点或那些点,不能构成dp[j][i]
。另外,为什么不能dp[j][i] = dp[j-1][i]+dis[j-1][j]
?很简单,因为i
那一路已经访问过j
了,不能重复访问,这个也适用于2
处。
再看2
处,首先按照1
处来写这两点就重了,中间点不可以重的,而且也是未定义值;然后,为什么1
处不能像2
处这样写?因为2
处i
和i-1
中间不差任何点!2
处这里小循环多次才能得到最终值,用到的历史值都已在上次大循环中生成。
最后,看这个返回的dp[n][n]
,也是答案,他为什么用dp[n-1][n]+dis[n-1][n]
来表示?为什么不能用dp[n-2][n]+dis[n-2][n]
来表示?因为:设想假如最终结果是一条路从1
遍历每个点到n
,另一条路从1
直接到n
。dp[n-2][n]
是不能表示为这种最终情况的子过程(上个过程)的。而dp[n-1][n]
可以表示为任何最终情况的子过程。
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <vector>
#include <cstring>
#include <string>
#include <cmath>
using namespace std;
const double INF = 1e9; // 这里是 double INF
const int MAXN = 201;
int N;
int x[MAXN];
int y[MAXN];
double dis[MAXN][MAXN];
double dp[MAXN][MAXN];
void getDis()
{
memset(dis, 0, sizeof dis);
for (int i = 1; i <= N; i++)
for (int j = i + 1; j <= N; j++) // 不用求dis[j][i],因为用不到
dis[i][j] = sqrt((double)((x[j] - x[i])*(x[j] - x[i]) + (y[j] - y[i])*(y[j] - y[i])));
}
double bitonic_tour() // 双调旅行商问题(TSP问题简化)
{
dp[1][2] = dis[1][2];
for (int i = 3; i <= N; i++)
{
dp[i - 1][i] = INF;
for (int j = 1; j <= i - 2; j++)
{
dp[j][i] = dp[j][i - 1] + dis[i - 1][i]; // 1
dp[i - 1][i] = min(dp[i - 1][i], dp[j][i - 1] + dis[j][i]); // 2
}
}
return dp[N][N] = dp[N - 1][N] + dis[N - 1][N]; // 3
}
int main()
{
for (; ~scanf("%d", &N);)
{
for (int i = 1; i <= N; i++)
scanf("%d%d", &x[i], &y[i]);
getDis();
printf("%.2lf\n", bitonic_tour());
}
return 0;
}