【动态规划】sicily1163

 

1163. Tour

题目大意：

就是一个双调旅程问题，从最左边的点走到最右边的点，然后从最右边走回最左边，问这段旅程的最短距离。

 

解题思路：

题目已经告诉我们，所有的点已经按照左到右的顺序输入了。

题目可以转换成，从第一个点出发，分两路A，B走，最后汇集到第n个点。

用动态规划：

dp[i][j]表示A到达i点，B到达j点时的最短路径。我们始终考虑i>=j，根据对称性可以得出其余解

于是dp[n][n]表示最终解。

 

当前的状态为dp[i][j]，分情况：

1. j != i - 1 时：此时dp[i-1][j]再通过从点i-1到i即可。
2. 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