uva 1347 动态规划DAG lrj-P269

el/2024/2/25 22:24:16

题意:

给出按照 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;
}



http://www.ngui.cc/el/4895178.html

相关文章

uva 116 动态规划 多阶段决策问题 路径记录 lrj-P270

题意&#xff1a; 给定一个n*m的矩阵&#xff0c;要求从第一列的任何一行出发&#xff0c;每次沿右或右下或右上到达后面一列&#xff0c;最后到第m列任何一行整个路程的最小值&#xff0c;并且要求是字典序最小的 题解&#xff1a; 动态规划 每一列是一个阶段&#xff…

uva 12563 01背包 两个最优条件 lrj-P274

题意&#xff1a; 给你 t 秒时间&#xff0c;有n首歌&#xff0c;每一首歌的时间不超过三分钟&#xff0c;在结束之前唱一首678秒的劲歌金曲 选了一首歌就一定要唱完 并且在保持唱的歌曲数量最多的情况下&#xff0c;时间最长 题解&#xff1a; 虽然 t 的范围很大&…

uva 11400 lrj-P275 动态规划

题意&#xff1a; 见刘汝佳入门书籍 P275 dp[i]min(dp[i],dp[j-1](sum[i]-sum[j-1])*a[i].ca[i].k);题解&#xff1a; 见刘汝佳入门书籍 P275 #include<stdio.h> #include<string.h> #include<algorithm> using namespace std;int dp[1010],sum[1010]; s…

密码生成器+随机数生成器

随机数生成器 0~RAND_MAX之间的随机数程序 #include <iostream> #include <stdlib.h> #include <time.h> using namespace std; int main() {srand((unsigned)time(NULL));for(int i = 0; i < 10; i++ )cout << rand() << \t;cout << …

uva 10003 lrj-P278 区间dp入门

题意&#xff1a; 给出一根棍子的长度&#xff0c;以及n个需要切割的点&#xff0c;每一次切割的代价是这一段需要被切割的长度 问代价最小时的代价值 题解&#xff1a; 区间dp dp[i][j]min(dp[i][j],dp[i][k]dp[k][j]a[j]-a[i]); i 为区间左端点&#xff0c;j 为右端点…

Uva-1626 lrj-P278 区间dp

题意&#xff1a; 给定一个由[,],(,)&#xff0c;构成的字符串&#xff0c;给其添加这些括号使得其成为一个正规括号序列 1 空序列是正规括号序列 2 如果S是正规括号序列&#xff0c;那么[S]和(S)也是正规括号序列 3 如果A和B都是正规括号序列&#xff0c;则AB也是正规…

uva 1331 lrj-P279 三角剖分+区间dp

题意&#xff1a; 给出多边形&#xff0c;找出最大三角形面积最小的三角剖分 输出最大的三角形面积 题解&#xff1a; 仔细研究可以知道&#xff0c;第一个点和最后一个点组成的边&#xff0c;一定是在某一个三角形中 那么我们就通过这个边作为基准&#xff0c;任选一个…

uva 12186 lrj-P282 简单树形dp

题意&#xff1a; 某个人签字的话,他的直属下属里必须有至少T%的人签字,问让老板签字最少需要多少工人签字 题解&#xff1a; 树形dp 以老板为根节点&#xff0c;从小往上&#xff0c;递归计算答案即可 #include<vector> #include<stdio.h> #include<st…

uva 1220 lrj-P282 最大独立集(树形dp)

题意&#xff1a; 给出一个树形结构&#xff0c;除了老板外&#xff0c;每一个员工都有直属上司&#xff0c;在其中挑选了员工&#xff0c;就不能挑选他的上司 问这样的挑选方法最多可以挑选多少人&#xff0c;方案是否唯一 题解&#xff1a; 仔细划分即可 当前节点若选…

uva 10285 lrj-P304 从简单DAG动态规划得到的感悟

题意&#xff1a; 给出一个整数矩阵&#xff0c;请找出一条严格递减的最长路的长度 题解&#xff1a; 分析&#xff1a; 1没有固定起点和终点 2是二元关系&#xff0c;也就是DAG&#xff08;有向无环图&#xff09; 3lrj书上此类一律都是用记忆化搜索 假设&#xff…