uva 1347 动态规划DAG lrj-P269

本文主要是介绍uva 1347 动态规划DAG lrj-P269，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题意：

给出按照 x 坐标排序的一系列二维坐标上的点，让你通过来回走一圈，把所有点都恰好走一遍，除了最左端和最右端的点

使得总路程最短

题解：

让两个人同时走，并且不重合，从左边开始走道右边去

令dp【i】【j】表示两个人分别走道  i  和走到  j 的时候的最短路

因为dp【i】【j】==dp【j】【i】

故强行令  i > j

然后dp【i】【j】可以转移到dp【i+1】【j】或者dp【i】【i+1】，后者要满足上叙条件，则等价于dp【i+1】【i 】

最后的两人都要到 n ，但是  i > j  所以最后要处理一下即可，见代码

#include<math.h>
#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;struct node
{int x,y;node(){}node(int x_,int y_){x=x_,y=y_;}
}p[200];
double dp[1010][1010];double dis(node p1,node p2){return sqrt((p1.x-p2.x)*(p1.x-p2.x)+(p1.y-p2.y)*(p1.y-p2.y));
}int main()
{int cases=1,n;//freopen("in.txt","r",stdin);while(scanf("%d",&n)!=EOF){for(int i=1;i<=n;i++)scanf("%d%d",&p[i].x,&p[i].y);dp[2][1]=dis(p[1],p[2]);for(int i=3;i<=n;i++){dp[i][i-1]=0x3f3f3f3f;for(int j=1;j<i-1;j++){dp[i][j]=dp[i-1][j]+dis(p[i],p[i-1]);dp[i][i-1]=min(dp[i][i-1],dp[i-1][j]+dis(p[j],p[i]));}}double ans=0x3f3f3f3f;for(int j=1;j<n;j++)ans=min(ans,dp[n][j]+dis(p[j],p[n]));printf("%0.2lf\n",ans);}return 0;
}

这篇关于uva 1347 动态规划DAG lrj-P269的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---