题意：

算法导论上的一道习题，给出一系列点的的坐标，现在从最左端出发，到达最右端的点，再返回原点，要求遍历所有点并且路程最短。

要点：

出发又返回可以看成两个人同时从左往右走，其中一个人走的快一个人走的慢。重点是因为一个点只能走一次，所以可以想出最优子结构，假设现在用dp[i][j]表示两个人分别走到点i和j的最短路径，下一步是走到i+1这个点，那么可能是位置为i的人走到，又或者是位置为j的人走到。可以写出状态转移方程：

dp[i + 1][i] = min(dp[i + 1][i], dp[i][j] + dis[i + 1][j])；i+1分配给位置为j的人

dp[i + 1][j] = min(dp[i + 1][j], dp[i][j] + dis[i][i + 1])；i+1分配给位置为i的人

我们最后要求的dp[n][n]一定是从dp[n][n-1]而来的，所以最后直接dp[n][n-1]+dis[n-1][n]就是答案。下面两个图可以方便理解。我写的时候用memset直接数组赋值，非常容易出错。

15903855

Accepted

440K

16MS

1024B

2016-08-06 07:57:38

#include
    
     #include
     
      #include
      
       using namespace std;struct node{	int x, y;}p[105];bool cmp(node a, node b){	return a.x < b.x;}int main(){	int n,i,j;	double dp[105][105], dis[105][105];	while (cin >> n)	{		for (i = 0; i < n; i++)			cin >> p[i].x >> p[i].y;		sort(p, p + n, cmp);		for (i = 0; i < n; i++)		{			dis[i][i] = 0;			for (j = i + 1; j < n; j++)				dis[j][i] = dis[i][j] = sqrt(pow((double)(p[i].x - p[j].x), 2.0) + pow((double)(p[i].y - p[j].y), 2.0));		}		for (i = 0; i < n; i++)			for (j = 0; j < n; j++)				dp[i][j] = 0xffffff;//直接用memset赋值就算是0x3f3f3f也不行		dp[1][0] = dis[1][0];//初始条件		for(i=0;i