2014
01-04

# 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;
}

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

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