紫书P269-uva1347题解,结合紫书解析加入了一些个人理解

2023-11-20 17:32

本文主要是介绍紫书P269-uva1347题解,结合紫书解析加入了一些个人理解,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

该题在vjudge上的链接
在紫书的动态规划那一节看到了这道题。结合刘汝佳的解析,在代码里加了一些个人的理解,已经提交UVA通过。

//将问题看做两个人从起点出发,不能走重复的点,计算两个人到达终点时走过的距离和
#include <bits/stdc++.h>
#define mem(a, b) memset(a, b, sizeof(a))
#define scf(a) scanf("%d", &a)
#define scf2(a, b) scanf("%d%d", &a, &b)
using namespace std;struct point
{int x, y;
} p[1001];//dp[i][j]表示一个人在i,一个人在j,二者到终点还差的距离和,且1到i的点已经全部走过
//因为dp[i][j]==dp[j][i],所以规定i>j,因为两人不能在同一个点,所以i!=j
//状态方程为dp[i][j]=min(dp[i+1][j]+dist(i,i+1),dp[i+1][i]+dist(j,i+1));
//一种是让处于i的人走,一种是让处于j的人走,且下一步必须走到i+1,不能走其他地方
//对于这种走法是否存在漏解的说明:这种走法依然能遍历到所有二者位置的状态,
//且在遍历dp[i][j]之前,dp[x>=i][y>=j]的结果都已确定(见cal函数的递归实现),可以保证dp[i][j]的正确性
double dp[1001][1001];double dist(int a, int b) //传入两个点的下标,计算二者距离
{int dx = p[a].x - p[b].x, dy = p[a].y - p[b].y;return sqrt(dx * dx + dy * dy);
}double cal(int i, int j) //计算并返回dp[i][j]的值,递归实现
{if (dp[i][j] != 0)return dp[i][j];//在两个人中选取一个人走到i+1//走了之后要加上dist(o->e)的距离dp[i][j] = min(cal(i + 1, j) + dist(i, i + 1), cal(i + 1, i) + dist(j, i + 1));return dp[i][j];
}int main()
{mem(dp, 0);int n;while (scf(n)!=EOF){mem(dp,0);for (int i = 1; i <= n; i++){scf2(p[i].x, p[i].y);}double dis = dist(n, n - 1); //n到n-1的距离,减少重复计算/*  计算一个人处于n-1,另一个人处于j时,距离终点还有多远,因为dp[i][j](i>j)表示i内的点都已经走过,所以dp[n-1][j]就只剩下了n可以走,所以距离是唯一确定的也就是n-1到n的距离加上j到n的距离*/for (int j = 1; j < n - 1; j++){dp[n - 1][j] = dis + dist(j, n);}printf("%.2lf\n", cal(2, 1) + dist(1, 2));}return 0;
}/*样例数据3
1 1
2 3
3 1
4
1 1
2 3
3 1
4 2*/

这篇关于紫书P269-uva1347题解,结合紫书解析加入了一些个人理解的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/396291

相关文章

PostgreSQL的扩展dict_int应用案例解析

《PostgreSQL的扩展dict_int应用案例解析》dict_int扩展为PostgreSQL提供了专业的整数文本处理能力,特别适合需要精确处理数字内容的搜索场景,本文给大家介绍PostgreS... 目录PostgreSQL的扩展dict_int一、扩展概述二、核心功能三、安装与启用四、字典配置方法

深度解析Java DTO(最新推荐)

《深度解析JavaDTO(最新推荐)》DTO(DataTransferObject)是一种用于在不同层(如Controller层、Service层)之间传输数据的对象设计模式,其核心目的是封装数据,... 目录一、什么是DTO?DTO的核心特点:二、为什么需要DTO?(对比Entity)三、实际应用场景解析

从原理到实战深入理解Java 断言assert

《从原理到实战深入理解Java断言assert》本文深入解析Java断言机制,涵盖语法、工作原理、启用方式及与异常的区别,推荐用于开发阶段的条件检查与状态验证,并强调生产环境应使用参数验证工具类替代... 目录深入理解 Java 断言(assert):从原理到实战引言:为什么需要断言?一、断言基础1.1 语

深度解析Java项目中包和包之间的联系

《深度解析Java项目中包和包之间的联系》文章浏览阅读850次,点赞13次,收藏8次。本文详细介绍了Java分层架构中的几个关键包:DTO、Controller、Service和Mapper。_jav... 目录前言一、各大包1.DTO1.1、DTO的核心用途1.2. DTO与实体类(Entity)的区别1

Java中的雪花算法Snowflake解析与实践技巧

《Java中的雪花算法Snowflake解析与实践技巧》本文解析了雪花算法的原理、Java实现及生产实践,涵盖ID结构、位运算技巧、时钟回拨处理、WorkerId分配等关键点,并探讨了百度UidGen... 目录一、雪花算法核心原理1.1 算法起源1.2 ID结构详解1.3 核心特性二、Java实现解析2.

Python中re模块结合正则表达式的实际应用案例

《Python中re模块结合正则表达式的实际应用案例》Python中的re模块是用于处理正则表达式的强大工具,正则表达式是一种用来匹配字符串的模式,它可以在文本中搜索和匹配特定的字符串模式,这篇文章主... 目录前言re模块常用函数一、查看文本中是否包含 A 或 B 字符串二、替换多个关键词为统一格式三、提

使用Python绘制3D堆叠条形图全解析

《使用Python绘制3D堆叠条形图全解析》在数据可视化的工具箱里,3D图表总能带来眼前一亮的效果,本文就来和大家聊聊如何使用Python实现绘制3D堆叠条形图,感兴趣的小伙伴可以了解下... 目录为什么选择 3D 堆叠条形图代码实现:从数据到 3D 世界的搭建核心代码逐行解析细节优化应用场景:3D 堆叠图

深度解析Python装饰器常见用法与进阶技巧

《深度解析Python装饰器常见用法与进阶技巧》Python装饰器(Decorator)是提升代码可读性与复用性的强大工具,本文将深入解析Python装饰器的原理,常见用法,进阶技巧与最佳实践,希望可... 目录装饰器的基本原理函数装饰器的常见用法带参数的装饰器类装饰器与方法装饰器装饰器的嵌套与组合进阶技巧

解析C++11 static_assert及与Boost库的关联从入门到精通

《解析C++11static_assert及与Boost库的关联从入门到精通》static_assert是C++中强大的编译时验证工具,它能够在编译阶段拦截不符合预期的类型或值,增强代码的健壮性,通... 目录一、背景知识:传统断言方法的局限性1.1 assert宏1.2 #error指令1.3 第三方解决

全面解析MySQL索引长度限制问题与解决方案

《全面解析MySQL索引长度限制问题与解决方案》MySQL对索引长度设限是为了保持高效的数据检索性能,这个限制不是MySQL的缺陷,而是数据库设计中的权衡结果,下面我们就来看看如何解决这一问题吧... 目录引言:为什么会有索引键长度问题?一、问题根源深度解析mysql索引长度限制原理实际场景示例二、五大解决