poj-2677 动态规划、双调欧几里得旅行商

Tour

Time Limit: 1000MS   Memory Limit: 65536K
Total Submissions: 2699   Accepted: 1193

Description

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. 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

题目大意:给出一些点的坐标,顺序为从左到右。飞行员小明要飞一段旅程。

分析:先略。

时间: 2015-06-17

poj-2677 动态规划、双调欧几里得旅行商的相关文章

POJ1061 扩展欧几里得

根据题意得出的方程 (m-n)t+Lk=y-x t为步数 k为圈数 然后根据扩展欧几里得就能得出解 然后处理一下就可以了 对L取余要防止负数情况 #include <iostream> #include<cstdio> using namespace std; void exgcd(long long a,long long b,long long &d,long long &x,long long &y) { if(b==0) { x=1;y=0;d=a;

POJ2115 扩展欧几里得

扩展欧几里得模板题 根据题意理出二元一次方程 A+X*C-B=Y*2^k 移项可得X*C+Y*2^k=B-A  然后扩展欧几里得 就得出答案了 #include <iostream> #include<cstdio> #include<cstring> using namespace std; void exgcd(long long a,long long b,long long &d,long long &x,long long &y) {

POJ2447 分解因数+扩展欧几里得+高次幂取模

昨天一天弄明白的pollard-rho启发式因数分解没想到今天就用上了 而且是一次过 感觉好有成就感  题目大意 给你N=P*Q 先把p q从N因数分解出来 得到具体的值 然后(p-1)*(q-1)=t 从而求出t的值 有了t的值 根据e*d(mod t)=1 求出e模t的逆元d 注意求出的逆元可能为负 然后求c^d%n 为m 就是 题目要求的值 这题的解题步骤如下 1根据pollard-rho启发式因数分解 把n分解成两个素数p q; 2(p-1)*(q-1)求出t的值 3通过扩展欧几里得 求

POJ 2142 扩展欧几里得

这题问的是|x|+|y|最小的时候 讨论一下当取x最小正整数解的时候 通过x求出y 当y取最小正整数解的时候通过y求出x  只有这两种情况因为情况的x和y都比这两种情况的大  所以只需要比较这两种情况的特解就可以得出答案 #include <iostream> #include<cstdio> #include<cstring> using namespace std; void exgcd(long long a,long long b,long long &

扩展欧几里得求两多项式最大公因式

#include <iostream> #include <string.h> #include <stdio.h> #include <math.h> using namespace std; typedef long long LL; const double eps = 1e-8; const int MOD = 999983; const int N = 55; struct Poly { int n; LL a[N]; }; Poly p[25];

POJ 1014 DP

这题我用DP做的 并且记住一定不要先对2取模 我一开始对2取模果断WA后来发现 如果是3 0 1 0 0 0 这种情况是可分的但是如果提前对2取模变成1 0 1 0 0 0 这种情况那么就不可分了 还有待于提高啊 看到一个神剪枝 1-6的最小公倍数是60 每个数量对60取余就行了 至于为什么 我是根据利用扩展欧几里得解多元不定方程逆着想通的 不知道还有没有更好的证明方法 #include <iostream> #include<cstdio> #include<cstring

英脱欧:政府承诺会试图养活欧盟支持过的英国科学

英脱欧(Brexit): 科学家和政治家都呼吁脱欧政府继续对欧盟支持的项目提供相同的资金支持,否则,英国有成为"死水一潭"的危险. 英国议会科学技术委员会主席Nicola Blackwood敦促脱欧政府尽快推出举措,向科学家和其欧盟合作者确保英国"仍会坚定地开放生意大门".她表示:"脱欧不可避免地会对英国在未来与欧盟的商讨各项条款时带来很大的不确定性.如果欧盟科研资金在将至的退欧谈判里受到影响,英国财政部可能要重新分配之前交给欧盟的资金." 她的

《体育帝国》游戏里坐飞机可免费获现实里程积分

赛迪网11月13日消息瑞士体育帝国公司今日确认,已与欧洲老牌航空公司法航达成协议,后者成为体育休闲网游<体育帝国>的专属航空公司,玩家在游戏里乘坐飞机将可免费获得法航里程积分,累积一定分数即可兑换免费法航机票. <体育帝国>是瑞士体育帝国公司开发的一款大型综合体育竞技网游,中国由巨人网络代理运营.业内人士指出,体育帝国公司与法国航空的合作开创了网游异业合作的全新领域. 据了解,<体育帝国>玩家加入法航蓝天俱乐部,即可用游戏里的机票兑换真实的里程数,攒够一定里程数可兑换免

【转载】计算机科学中最重要的32个算法

     奥地利符号计算研究所(Research Institute for Symbolic Computation,简称RISC)的Christoph Koutschan博士在自己的页面上发布了一篇文章,提到他做了一个调查,参与者大多数是计算机科学家,他请这些科学家投票选出最重要的算法,以下是这次调查的结果,按照英文名称字母顺序排序. A* 搜索算法--图形搜索算法,从给定起点到给定终点计算出路径.其中使用了一种启发式的估算,为每个节点估算通过该节点的最佳路径,并以之为各个地点排定次序.算法