本文主要是介绍Hdu 2224 The shortest path(双调TSP),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=2224
The shortest path
Time Limit: 1000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 654 Accepted Submission(s): 335
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.
3 1 1 2 3 3 1
6.47Hint: The way 1 - 3 - 2 - 1 makes the shortest path.
题意:给n个二维点,你要先沿x坐标严格递增的方向从1点走到n点,然后在沿x坐标严格递减的方向从n点走到1点,求走过的路程和的最小值。
分析:可以将上述的一条路看成从1点到n点的没有交叉点的两条路A和B。 两条路分别从 点1 向x递增的方向 A走到 i,B走到 j 。
就可以定义 dp[i][j] 为A走到 i ,B走到 j 的最短距离。题目就变成了 求dp[n][n]的值。
转移方程:
dp[1][2] = D[i][j]; //i ,j 两点的真实距离。
i < j-1 时; dp[ i ][ j ] = dp[ i ][ j-1] + D[ j-1 ][ j ];
i == j-1 时;dp[ i ][ j ] = min(dp[ k ][ j-1 ] + D[ k ][ j ]);
dp[ n ][ n ] = dp[ n-1 ][ n ]+ D[ n-1 ][ n ].
代码:
#include<cmath>
#include<cstdio>
#include<algorithm>
using namespace std;
#define MAX 205
#define inf 9999999
double dp[MAX][MAX];
double D[MAX][MAX];
struct node
{double x,y;
}p[MAX];
int cmp(const void *a,const void *b)
{struct node *p = (struct node *)a;struct node *q = (struct node *)b;return (p->x - q->x >0)?1:-1;
}
double dis(node a,node b)
{return sqrt(pow(a.x-b.x,2)+pow(a.y-b.y,2));
}
void init(int n)
{for (int i = 1; i <= n; i++)for (int j = 1; j <= n; j++){D[i][j] = inf;}
}
int main()
{int n;while(scanf("%d",&n)!=EOF){init(n);for (int i = 1;i<=n;i++){scanf("%lf %lf",&p[i].x,&p[i].y);for(int j=1;j<i;j++)D[i][j]=D[j][i] = dis(p[i],p[j]);//记录直接距离。}qsort(p+1,n,sizeof(p[1]),cmp);dp[1][2] = D[1][2];for (int i = 3; i <= n; i++){for (int j = 1; j <= i-2; j++)//when i-1 in the higher dir{dp[j][i] = dp[j][i-1] + D[i-1][i];}double Min = inf;for (int j = 1; j <= i-2; j++)//when i-1 in the lower dir{Min = min(dp[j][i-1]+D[j][i],Min);}dp[i-1][i] = Min;}dp[n][n] = dp[n-1][n]+D[n][n-1];printf("%.2lf\n",dp[n][n]);}return 0;
}
这篇关于Hdu 2224 The shortest path(双调TSP)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!