UVA 1347 Tour 双调旅行商

题意：平面上有N个点。一个人要从左上角的点向右走，到右下角的点，然后再回到左上角的点。现在想让这个人每个点到达一次，且走的总路程的距离最小。求出最小的距离。
思路：双调旅行商问题。
因为起点和中途点已知，我们可以把这个问题转化成两个人从左上角出发，分别不重复的到达其他点，最后在右下角的点汇合。
可以注意到，在这个过程中，两个人位于的点，他们经过的点，这三个就可以描述他们的状态。
定义dp[i][j]为一个人在点i,一个人在点j,他们经过了前$max(i,j)$个城市，因为两个人的顺序可以发生变化，我们令$i\ge j$是不会影响状态的。
但是该怎么样进行状态转移呢？注意到$dp[i][j]$表示他们已经走完了前i个城市，那为了保持定义，我们必须下一个状态走完前i+1个城市。但是由两个人中的谁去呢？这个需要进行决策。
所以状态转移方程是：

#include 
#include 
#include 
#include using namespace std;const int MAX = 1010;int x[MAX],y[MAX];
double d[MAX][MAX];
double dp[MAX][MAX];int main(void)
{//freopen("input.txt","r",stdin);int N;while(scanf("%d",&N) != EOF){for(int i = 1; i <= N; ++i)scanf("%d%d",&x[i],&y[i]);for(int i = 1; i <= N; ++i){for(int j = 1; j < i; ++j){double dx = x[i]-x[j];double dy = y[i]-y[j];d[i][j] = d[j][i] = sqrt(dx*dx+dy*dy);}d[i][i] = 0.0;}for(int i = 1; i <= N; ++i)dp[N][i] = d[i][N];for(int i = N - 1; i >= 1; --i)for(int j = 1; j <= i; ++j)dp[i][j] = min(dp[i+1][j] + d[i][i+1],dp[i+1][i] + d[j][i+1]);printf("%.2f\n",dp[1][1]);}return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！