Tour UVA - 1347 (DP)

本文主要是介绍Tour UVA - 1347 (DP)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

https://vjudge.net/problem/38898/origin

题目大意和题解过程详见紫书p269

ps:我只说一下自己的理解：

 首先这个题有一个关键词是“输入的数据是根据x坐标的顺序输入的且没有重复的”，那么这说明要想把这个多变形链接起来，那首先得有一条路径从起点到终点，在有一条路径从终点到起点。相当于从起点有两条路径到达终点。那么要想让这两条路径最短该怎么办呢？ 可以肯定的是点n-1一定是链接n的，这只是一条，那另一条的话就是其他的一个点了，当在状态(n-1,j)的时候有，即边界为dp[n-1][j]=dist[n-1][j]+dist[n-1][n]

倒着递推会求出dp[2][1]，即最后的两个点，那么在求出从1到2的距离就是所求了。

dp[i][j]=min(dp[i+1][j]+dist[i][i+1],dp[i+1][i]+dist[j][i+1]);

对于这个状态转移方程也不用多说了

其他的题解在紫书上很详细

#include <iostream>
#include <bits/stdc++.h>using namespace std;struct node
{int x;int y;
} q[1000];double dist[1000][1000];
double dp[1000][1000];double getd(int i,int j)
{return sqrt((q[i].x-q[j].x)*(q[i].x-q[j].x)*1.0+(q[i].y-q[j].y)*(q[i].y-q[j].y)*1.0);
}
int main()
{int n;while(~scanf("%d",&n)){if(n<=1){printf("0.00\n");continue;}for(int i=1; i<=n; i++){scanf("%d%d",&q[i].x,&q[i].y);}for(int i=1; i<=n; i++){for(int j=1; j<=n; j++){dist[i][j]=getd(i,j);}}for(int i=n-1; i>=1; i--){for(int j=1; j<i; j++){if(i==n-1){dp[i][j]=dist[i][n]+dist[j][n];}else{dp[i][j]=min(dp[i+1][j]+dist[i][i+1],dp[i+1][i]+dist[j][i+1]);}}}printf("%.2lf\n",dp[2][1]+dist[1][2]);}return 0;
}

这篇关于Tour UVA - 1347 (DP)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---