1163. Tour
题目大意:
就是一个双调旅程问题,从最左边的点走到最右边的点,然后从最右边走回最左边,问这段旅程的最短距离。
解题思路:
题目已经告诉我们,所有的点已经按照左到右的顺序输入了。
题目可以转换成,从第一个点出发,分两路A,B走,最后汇集到第n个点。
用动态规划:
dp[i][j]表示A到达i点,B到达j点时的最短路径。我们始终考虑i>=j,根据对称性可以得出其余解
于是dp[n][n]表示最终解。
当前的状态为dp[i][j],分情况:
- j != i - 1 时:此时dp[i-1][j]再通过从点i-1到i即可。
- j == i - 1 or j == i时:此时需要遍历取最小值
代码如下:
/*
* main.cpp
*
* Created on: Sep 24, 2011
* Author: raphealguo
*/
#include <stdio.h>
#include <iostream>
#include <string.h>
#include <math.h>
using namespace std;
#define MAXL 1010
struct Point{
int x;
int y;
};
double dis(Point p1, Point p2){
return sqrt((p1.x-p2.x)*(p1.x-p2.x) + (p1.y-p2.y)*(p1.y-p2.y));
}
int main(){
int n;
int i, j;
Point p[MAXL];
double dp[MAXL][MAXL];
while (scanf ("%d", &n) != EOF){
for (i = 1; i <= n; ++i){
scanf("%d %d", &p[i].x, &p[i].y);
}
memset(dp, 0, sizeof(dp));
dp[1][1] = 0;
for (i = 1; i <= n; ++i){
for (j = 1; j < i; ++j){
if (dp[i][j] == 0){//第一次赋值
dp[i][j] = dp[i-1][j] + dis(p[i], p[i-1]);
}else{
dp[i][j] = min(dp[i][j], dp[i-1][j] + dis(p[i], p[i-1]));
}
if (dp[i][i-1] == 0){//第一次赋值
dp[i][i-1] = dp[i-1][j] + dis(p[i], p[j]);
}else{
dp[i][i-1] = min(dp[i][i-1], dp[i-1][j] + dis(p[i], p[j]));
}
if (dp[i][i] == 0){//第一次赋值
dp[i][i] = dp[i][j] + dis(p[i], p[j]);
}else{
dp[i][i] = min(dp[i][i], dp[i][j] + dis(p[i], p[j]));
}
}
}
printf ("%.2lf\n", dp[n][n]);
}
return 0;
}
附带原题:
1163. Tour
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 = . 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
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
分享到:
相关推荐
sicily部分源代码,全都亲测,可通过
中大sicily online judge的刷题指南,里面介绍得很详细,不过,最近sicily好像不能外网访问了。
sicily 1562_LVM.cpp参考代码
112页的大礼包,sicily的部分ac代码。
本cpp是sicily的1006的解题代码 这份代码以最简单的方式实现了它的功能要求 值得学习一番
Sicily的题目分类:各种题目的分类,大致方法,以及题目难度规范
sicily1007题答案,附代码解释,可以在平台上通过
sicily 1274的AC源码,通过且速度快,适合学生使用
中山大学 ACM sicily 1294 题目代码
对于二叉树T,可以递归定义它的先序遍历、中序遍历和后序遍历如下: PreOrder(T)=T的根节点+PreOrder(T的左子树)+PreOrder(T的右子树) InOrder(T)=InOrder(T的左子树)+T的根节点+InOrder(T的右子树) PostOrder(T)=...
本程序解决了Sicily平台上Queue的问题,有较好的可读性
sicily(soj) 1022 1064 1310 1740 1876 1934 六题的源代码(数据结构综合应用题)
sicily 1817和1818的程序,各有两种方法,供参考。
本程序是中山大学sicily 1004-1007-1010-1014-1021 参考代码
本程序是中山大学sicily-1137-1145-1146-1147-1154-1157-1194的代码
本程序是中山大学sicily上1200-1221-1298-1324-1325的参考代码。
包括 sicily online judge 1149等部分题目,线性表,最小生成树,中缀转后缀并计算后缀表达式等。
此处是sicily 1093,1888 c++的源代码
Sicily Online Judge,原题代码