UVA1347 Tour

2023-12-08 08:08
文章标签 tour uva1347

本文主要是介绍UVA1347 Tour,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

2021.5.22
刷题的时候突然看到手机推送,袁隆平院士逝世,心中一颤,后来得到辟谣,心情稍微放松几分,正在刷着辟谣的文章时,央视新闻发文,13点07分,袁隆平院士逝世,没过多久又看到吴孟超院士逝世的新闻,心情难以平复,特在本文的开头,向两位院士致敬。
历史浩荡,国士无双。

UVA1347 Tour

题目链接

dp题,按照紫书上的分析做下来的,下面主要也是跟着紫书走一遍。

题目分析

“从左到右再回来”不太方便思考,可以改成:两个人同时从最左点出发,沿着两条不同的路径走,最后都走到最右点,且除了起点和终点外其余每个点恰好被一个人经过。这样,就可以用d(i,j)表示一个人走到i,另一个人走到j,还需要走的距离。
但是,如此定义,很难保证两个人不会走到同一点。
下面修改一下,d(i,j)表示从1~max(i,j)全部走过,且当前两人一个在i一个在j还需要走的距离,并且规定下一步只能走到i+1,即下一个状态为d(i+1,j)或d(i+1,i)(相当于从j点到i+1)我们规定把大的序号放在前面,否则可能会出现死循环。
边界条件是d(n-1,j)=dist(n-1,n)+dist(j,n),dist表示两点间的距离
状态转移方程为d(i,j) = min(d(i + 1, j) + dist(i, i + 1), d(i + 1, i) + dist(j, i + 1))

AC代码

#include<iostream>
#include<cmath>
#include<iomanip>
#include<cstring>
#include<algorithm>
using namespace std;
const int MAXN = 1000 + 10;
struct point
{int x, y;point(int a = 0, int b = 0){x = a;y = b;}
};
point points[MAXN];
double distance(int i, int j)
{point a = points[i];point b = points[j];double dis = sqrt(pow((a.x - b.x), 2) + pow((a.y - b.y), 2));return dis;
}
int n;
double dp[MAXN][MAXN];
double d(int i, int j)
{if (dp[i][j] > 0)return dp[i][j];if (i == n - 1)return dp[i][j] = distance(i, n) + distance(j, n);return dp[i][j] = min(d(i + 1, j) + distance(i, i + 1), d(i + 1, i) + distance(j, i + 1));
}
int main()
{while (cin >> n){memset(dp, 0, sizeof(dp));for (int i = 1; i <= n; i++){cin >> points[i].x >> points[i].y;}cout << fixed << setprecision(2) << d(2, 1) + distance(1, 2) << endl;}
}

这篇关于UVA1347 Tour的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/469138

相关文章

【SPOJ】1825 Free tour II 点分治

传送门:【SPOJ】1825 Free tour II 题目分析:敲了两遍。。。 本题是论文题,具体见漆子超论文《分治算法在树的路径问题中的应用》。 在以root为根的第 i 棵子树上,我们用G[ i ,j ]表示root的第 i 棵子树的路径上严格有 j 个黑点的路径的最长长度。用F[ i ,j ]表示在root为根的第 i 棵子树的路径上不超过 j 个黑点的路径的最长长度。因

ZOJ 1992 Sightseeing Tour

题意: 判断混合图欧拉回路 思路: (欧拉回路整理 参考 http://zhyu.me/acm/zoj-1992-and-poj-1637.html 和 http://blog.csdn.net/zxy_snow/article/details/6230223) 1.无向图:图连通,且图中均为偶度顶点。 2.有向图:图连通,且图中所有顶点出入度相等。 3.混合图:混合图欧拉回

CodeForces 490F Treeland Tour

题意: 一棵树(6000个节点)每个点上有个值  对于它里面的每一条路径可以用路径上的点的值的LIS来表示  问  这样的LIS最长有多长 思路: 枚举节点当开头复杂度O(n)  在树里面做LIS复杂度O(nlogn)  总共O(n^2logn) 应该没有难度  做LIS的时候类似线性序列  用栈维护  dfs时候记得回溯就好 PS:正解应该不是这样的  不过数据好小 代码:

hdu 1224 Free DIY Tour(最长路/dp)

http://acm.hdu.edu.cn/showproblem.php?pid=1224 基础的求最长路以及记录路径。感觉dijstra不及spfa好用,wa了两次。 #include <stdio.h>#include <algorithm>#include <set>#include <map>#include <vector>#include <math.h>#

C++概观:并发及实用工具(A Tour of C++: Concurrency and Utilities)

(说明:本章内容讲的主要是 c++11 标准相对于之前的标准新增加的内容。本书作者是 c++ 之父 Bjarne Stroustrup,这位作者的行文风格就是站在c++的设计者角度进行讲解,内容极其丰富,但并没有像传统编程书籍那样事无具细地罗列知识点,而是抓要点进行讲解,让你能够明白很多本质的东西。读者应当注意的是,作者的风格像是在和读者聊天,在聊天过程中透露他的要点。读者应注意作者的每一段描述,

SPOJ 1825 FTOUR2 - Free tour II (树上点分治)

题目地址:SPOJ 1825 树分治的题果然除了模板题就是金牌题啊。。。这题是一道论文题,想了好长时间。。。。终于过了,,,,注意一个坑点,如果权值全部为负的话,是可以不选任意一条边的,这样权值为0。。。也就是说初始值要设为0。。。 具体看漆子超的论文《分治算法在树的路径问题中的应用》。。 代码如下: #include <iostream>#include <string.h>#inc

poj 2135 Farm Tour(最小费用流)

思路: 求往返不能经过同一条道路两次,参观路线最小的最小值.可以转话为边的流量为1,总流量为2的最小费用流 约束: 1<= N <= 1000 1<= M <= 10000 1<= ai, bi <= N 1 <= ci <= 35000 /************************************************ Author: fisty* Create

SPOJ 1825 Free tour II

论文题: 在以root为根的第 i 棵子树上,我们用G[ i ,j ]表示root的第 i 棵子树的路径上严格有 j 个黑点的路径的最长长度。用F[ i ,j ]表示在root为根的第 i 棵子树的路径上不超过 j 个黑点的路径的最长长度。 因为所有子树里包含黑点数最多的路径的包含黑点数len可以O(N)求出,我们按照每棵子树的len从小到大的顺序遍历,这样就能将G和F数组降低一维,以G[ i

bfs+枚举,CF666B - World Tour

一、题目 1、题目描述 2、输入输出 2.1输入 2.2输出 3、原题链接 Problem - 666B - Codeforces 二、解题报告 1、思路分析 数据量允许跑N次bfs预处理所有点的最短路,以及预处理到达每个点距离最远的3个点,以及每个点能够到达的最远的3个点 我们枚举<b, c>,然后枚举 到达b的最远点a,c能到达的最远点

Codeforces 490F Treeland Tour(dp)

题目链接:Codeforces 490F Treeland Tour 类似于nlogn的递增上升子序列算法。 #include <cstdio>#include <cstring>#include <vector>#include <algorithm>using namespace std;const int maxn = 6005;const int inf = 0x3f3f