Tour - UVA - 1347-动态规划
发布日期:2022-02-10 08:11:10
浏览次数:19
分类:技术文章
本文共 2600 字,大约阅读时间需要 8 分钟。
***Tour ***
John Doe, a skilled pilot, enjoys traveling. While on vacation, he rents a small plane and starts visiting beautiful places. To save money, John must determine the shortest closed tour that connects his destinations. Each destination is represented by a point in the plane pi =< xi , yi >. John uses the following strategy: he starts from the leftmost point, then he goes strictly left to right to the rightmost point, and then he goes strictly right back to the starting point. It is known that the points have distinct x-coordinates. Write a program that, given a set of n points in the plane, computes the shortest closed tour that connects the points according to John’s strategy. Input The program input is from a text file. Each data set in the file stands for a particular set of points. For each set of points the data set contains the number of points, and the point coordinates in ascending order of the x coordinate. White spaces can occur freely in input. The input data are correct. Output For each set of data, your program should print the result to the standard output from the beginning of a line. The tour length, a floating-point number with two fractional digits, represents the result. Note: An input/output sample is in the table below. Here there are two data sets. The first one contains 3 points specified by their x and y coordinates. The second point, for example, has the x coordinate 2, and the y coordinate 3. The result for each data set is the tour length, (6.47 for the first data set in the given example). Sample Input 3 1 1 2 3 3 1 4 1 1 2 3 3 1 4 2 Sample Output 6.47 7.89题意:按照横坐标从左到右给出n个点,设计一条路线,从最左点出发到最右点后再返回,除最左点和最右点外,每个点只经过一次,求最短路径长度
解题思路:参考《算法竞赛入门经典》P269#include#include #include #include #include #include #include #include #include #define maxn 50005using namespace std;typedef long long ll;int n;struct F{ int x,y;};F point[1005];double dist[1005][1005];double d[1005][1005];double dp(int i,int j){ if(d[i][j]) return d[i][j]; if(i==n-1) return dist[n-1][n]+dist[j][n]; else return d[i][j]=min(dp(i+1,j)+dist[i][i+1],dp(i+1,i)+dist[j][i+1]);//记得保存在数组中,否则会超时}int main(){ while(scanf("%d",&n)==1) { memset(d,0,sizeof(d)); for(int i=1;i<=n;i++) scanf("%d%d",&point[i].x,&point[i].y); for(int i=1;i<=n;i++) for(int j=i+1;j<=n;j++) dist[i][j]=dist[j][i]=sqrt((point[i].x-point[j].x)*(point[i].x-point[j].x)+(point[i].y-point[j].y)*(point[i].y-point[j].y)); printf("%.2f\n",dp(2,1)+dist[1][2]); } return 0;}
不过我有一个疑问,按照书中的思路,点1到2的边一定经过,为什么该题的最短路径一定包含点1到2的边?
转载地址:https://blog.csdn.net/qq_44632981/article/details/98645793 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
关注你微信了!
[***.104.42.241]2024年03月31日 14时45分30秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
Web002-IIS安装是否成功测试.docx
2021-06-30
Emacs-024-光标修改为竖线
2021-06-30
Emacs-028-文本编辑中的删除操作
2021-06-30
Emacs-032-关闭当前Buffer
2019-04-27
Emacs-102-spacemacs使用vim导航键在文件清单中移动
2019-04-27
Emacs-103-使用spacemacs自带配置显示行号
2019-04-27
Emacs-204-company popup功能失效
2019-04-27
Emacs-205-Emacs的管理模块化
2019-04-27
Emacs-206-Windows上实现org-pomodoro的声音提示播放
2019-04-27
Emacs-207-Emacs org-mode与主题
2019-04-27
Emacs-208-搜索工程中的文件
2019-04-27
Emacs-209-使用projectile管理工程
2019-04-27
Emacs-210-使用projectile生成工程TAGS
2019-04-27
Emacs-211-在工程管理中跳转到指定的函数或变量定义位置
2019-04-27
Emacs-212-跳转到工程根目录
2019-04-27
Emacs-213-在工程中搜索
2019-04-27
Emacs-214-光标在不同的缩进中间跳转
2019-04-27
Emacs-217-默认打开当前文件所在目录的目录树
2019-04-27
Emacs-218-增加语义分析
2019-04-27
Emacs_234_子层级自动缩进功能
2019-04-27