首页 > ACM题库 > HDU-杭电 > hdu 2224 The shortest path-动态规划-[解题报告]C++
2014
01-04

hdu 2224 The shortest path-动态规划-[解题报告]C++

The shortest path

问题描述 :

There are n points on the plane, Pi(xi, yi)(1 <= i <= n), and xi < xj (i<j). You begin at P1 and visit all points then back to P1. But there is a constraint:
Before you reach the rightmost point Pn, you can only visit the points those have the bigger x-coordinate value. For example, you are at Pi now, then you can only visit Pj(j > i). When you reach Pn, the rule is changed, from now on you can only visit the points those have the smaller x-coordinate value than the point you are in now, for example, you are at Pi now, then you can only visit Pj(j < i). And in the end you back to P1 and the tour is over.
You should visit all points in this tour and you can visit every point only once.

输入:

The input consists of multiple test cases. Each case begins with a line containing a positive integer n(2 <= n <= 200), means the number of points. Then following n lines each containing two positive integers Pi(xi, yi), indicating the coordinate of the i-th point in the plane.

输出:

The input consists of multiple test cases. Each case begins with a line containing a positive integer n(2 <= n <= 200), means the number of points. Then following n lines each containing two positive integers Pi(xi, yi), indicating the coordinate of the i-th point in the plane.

样例输入:

3
1 1
2 3
3 1

样例输出:

6.47

Hint: The way 1 - 3 - 2 - 1 makes the shortest path.

点击打开链接

#include"stdio.h"
#include"string.h"
#include"math.h"
#define N 201
#define inf 99999999
struct node
{
	int x,y;
}A[N];

double D[N][N];
double dp[N][N];
double dis(int a,int b)
{
	return sqrt((double)(A[a].x-A[b].x)*(A[a].x-A[b].x)
		+(A[a].y-A[b].y)*(A[a].y-A[b].y));
}
int main()
{
	int n;
	int i,j;
	while(scanf("%d",&n)!=-1)
	{
		for(i=0;i<n;i++)
		{
			for(j=0;j<n;j++)
				D[i][j]=inf;
		}
		for(i=0;i<n;i++)
		{
			scanf("%d%d",&A[i].x,&A[i].y);
			for(j=0;j<i;j++)
				D[j][i]=dis(i,j);
		}
		dp[0][1]=D[0][1];
		for(j=2;j<n;j++)
		{
			for(i=0;i<=j-2;i++)//j-1在递增序列
				dp[i][j]=dp[i][j-1]+D[j-1][j];

			dp[j-1][j]=inf;
			for(i=0;i<=j-2;i++)//j-1在递减序列
				if(dp[i][j-1]+D[i][j]<dp[j-1][j])
					dp[j-1][j]=dp[i][j-1]+D[i][j];
		}
		dp[n-1][n-1]=dp[n-2][n-1]+D[n-2][n-1];
		printf("%.2f\n",dp[n-1][n-1]);
	}
	return 0;
}

解题转自:http://blog.csdn.net/yangyafeiac/article/details/9385253


  1. 我还有个问题想请教一下,就是感觉对于新手来说,递归理解起来有些困难,不知有没有什么好的方法或者什么好的建议?

  2. 我还有个问题想请教一下,就是感觉对于新手来说,递归理解起来有些困难,不知有没有什么好的方法或者什么好的建议?