首页 > 代码库 > UVa 1347 (双线程DP) Tour
UVa 1347 (双线程DP) Tour
题意：
平面上有n个坐标均为正数的点，按照x坐标从小到大一次给出。求一条最短路线，从最左边的点出发到最右边的点，再回到最左边的点。除了第一个和最右一个点其他点恰好只经过一次。
分析：
可以等效为两个人从第一个点出发，沿不同的路径走到最右点。
d(I, j)表示点1~max(I, j)这些点全部都走过，而且两人的位置分别是i和j，最少还需要走多长的距离。由这个定义可知，d(I, j) == d(j, i)，所以我们再加一个条件，d(I, j)中i>j
这样状态d(I, j)只能转移到d(i+1, j)和d(i+1, i)
边界：d(n-1, j) = dist(n-1, n) + dist(j, n) (1 ≤ j < n-1)
最终所求答案就是dist(1, 2) + d(1, 2)
1 //#define LOCAL 2 #include <iostream> 3 #include <cstdio> 4 #include <cstring> 5 #include <cmath> 6 using namespace std; 7 8 const int maxn = 1000 + 10; 9 double x[maxn], y[maxn], dp[maxn][maxn], dis[maxn][maxn];10 11 double dist(int a, int b)12 {13 return sqrt((double)(x[a]-x[b])*(x[a]-x[b]) + (y[a]-y[b])*(y[a]-y[b]));14 }15 16 int main(void)17 {18 #ifdef LOCAL19 freopen("1347in.txt", "r", stdin);20 #endif21 22 int n;23 while(scanf("%d", &n) == 1)24 {25 for(int i = 1; i <= n; ++i) scanf("%lf%lf", &x[i], &y[i]);26 for(int i = 2; i <= n; ++i)27 for(int j = 1; j < i; ++j)28 dis[i][j] = dis[j][i] = dist(i, j);29 for(int i = n - 1; i > 1; --i)30 for(int j = 1; j < i; ++j)31 {32 if(i == n - 1) dp[i][j] = dis[j][n] + dis[i][n];33 else dp[i][j] = min(dp[i+1][j] + dis[i][i+1], dp[i+1][i] + dis[i+1][j]);34 }35 printf("%.2lf\n", dis[1][2] + dp[2][1]);36 }37 38 return 0;39 }
UVa 1347 (双线程DP) Tour
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。