蓝桥杯(路径 动态规划 C++)

 思路:

1、利用动态规划的思想。

2、用f[i]来记录从第一个点到第i个点的最短距离。

3、f[i]赋值分两种情况,第一种:f[i]为0的时候,也就是第一种刚到i点的情况,记录其距离为最小公倍数;第二种:f[i]已经有值了,比较新的点到其距离和之前点到其距离,取小的赋值。

4、最后输出f[2021]就是第一个点到第2021个点的最短距离。

#include<iostream>
using namespace std;
int gcd(int x, int y)//辗转相除法,求最大公约数
{return !y ? x : gcd(y, x % y);
}
int main()
{int f[2030]={0};//记录到该点的最短距离for(int i=1;i<=2021;i++)for (int j = i + 1; j <= i + 21; j++){if (j > 2021)break;if (f[j] == 0)f[j] = f[i] + i * j / gcd(i, j);elsef[j] = min(f[j], f[i] + i * j / gcd(i, j));}cout << f[2021] << endl;
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/169060.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

2023年【危险化学品生产单位主要负责人】考试报名及危险化学品生产单位主要负责人模拟考试题

题库来源&#xff1a;安全生产模拟考试一点通公众号小程序 危险化学品生产单位主要负责人考试报名考前必练&#xff01;安全生产模拟考试一点通每个月更新危险化学品生产单位主要负责人模拟考试题题目及答案&#xff01;多做几遍&#xff0c;其实通过危险化学品生产单位主要负…

Plex Media Server for Mac: 打造您的专属媒体库

在数字媒体时代&#xff0c;我们越来越依赖各种媒体应用来丰富我们的生活。其中&#xff0c;Plex Media Server for Mac以其高效、稳定和多功能性&#xff0c;逐渐成为了Mac用户们的首选。今天&#xff0c;我们就来深入探讨这款个人媒体软件的优势和应用场景。 Plex Media Serv…

Kafka与MySQL的组合使用

根据上面给出的student表&#xff0c;编写Python程序完成如下操作&#xff1a; &#xff08;1&#xff09;读取student表的数据内容&#xff0c;将其转为JSON格式&#xff0c;发送给Kafka&#xff1b; 创建Student表的SQL语句如下&#xff1a; create table student( sno ch…

类似东郊到家预约家政保洁小程序搭建

随着生活水平的提高&#xff0c;人们对健康养生的需求越来越重视&#xff0c;按摩作为一种传统的养生方式&#xff0c;备受关注。为了方便用户快速、方便地预约按摩服务&#xff0c;本文将介绍一款按摩预约小程序的开发。 首先&#xff0c;我们通过市场调研和分析发现&#xf…

网络协议--IP:网际协议

3.1 引言 IP是TCP/IP协议族中最为核心的协议。所有的TCP、UDP、ICMP及IGMP数据都以IP数据报格式传输&#xff08;见图1-4&#xff09;。许多刚开始接触TCP/IP的人对IP提供不可靠、无连接的数据报传送服务感到很奇怪。 不可靠&#xff08;unreliable&#xff09;的意思是它不能…

2023年中国监控光端机优点、市场规模及发展前景分析[图]

监控光端机是一种用于光纤通信网络的设备&#xff0c;用于连接光纤到用户设备&#xff08;如计算机、路由器等&#xff09;。监控光端机行业涉及制造、销售和维护这些设备&#xff0c;以确保高速、稳定的光纤通信连接&#xff0c;适用于家庭、企业和数据中心等不同应用场景。 …

Python创建条形图加点重叠

目录 代码效果图 要使用Python的Seaborn库创建一个条形图加点重叠的统计图&#xff0c;可以使用 seaborn.barplot和 seaborn.stripplot函数。以下是一个论文级别的简单示例代码&#xff0c;演示如何创建这种效果的图 代码 import seaborn as sns import matplotlib.pyplot a…

MSQL系列(七) Mysql实战-SQL语句Join,exists,in的区别

Mysql实战-SQL语句Join&#xff0c;exists&#xff0c;in的区别 前面我们讲解了索引的存储结构&#xff0c;BTree的索引结构&#xff0c;以及索引最左侧匹配原则及讲解一下常用的SQL语句的优化建议&#xff0c;今天我们来详细讲解一下 我们经常使用的 join&#xff0c; exist&…

一种融合偶然和认知不确定性的贝叶斯深度学习RUL框架

_原文&#xff1a; _《《A Bayesian Deep Learning RUL Framework Integrating Epistemic and Aleatoric Uncertainties》 _作者__&#xff1a; _Gaoyang Lia&#xff0c;Li Yangb&#xff0c;Chi-Guhn Leec&#xff0c;Xiaohua Wangd&#xff0c;Mingzhe Ronge _作者单位&am…

统信uos 1030 企业版 安装.net core环境

安装.net core步骤 添加密钥和包存储库 安装 .NET 之前&#xff0c;请运行以下命令&#xff0c;将 Microsoft 包签名密钥添加到受信任密钥列表&#xff0c;并添加包存储库wget https://packages.microsoft.com/config/debian/10/packages-microsoft-prod.deb -O packages-mic…

VMwarePlayer安装Ubuntu,切换中文并安装中文输入法

1.下载和安装 虚拟机使用的免费版官网链接&#xff1a;VMwarePlayer Ubuntu镜像下载官网链接&#xff1a;Ubuntu桌面版 自己学习使用&#xff0c;不需要考虑迁移之类的。选择单个磁盘IO性能会更高 安装过程中如果出现如下报错&#xff0c;则用系统管理员身份运行 右击VMwa…

18-spring 事务

文章目录 1. xml和注解配置方式的对象2.spring事务传播特性3. 注解事务的初始化流程4. 创建事务信息流程图5. 事务回滚流程图 1. xml和注解配置方式的对象 2.spring事务传播特性 事务传播行为类型说明PROPAGATION_REQUIRED如果当前没有事务&#xff0c;就新建一个事务&#xf…

Docker 的数据管理与网络通信以及Docker镜像的创建

目录 Docker的数据管理 1、数据卷 2、数据卷容器 3、端口映射 4、容器互联 二、Docker网络 1、Docker网络实现原理 2、Docker的网桥模式 1&#xff09;Host 2&#xff09;Container 3&#xff09;none 4&#xff09;bridge 5&#xff09;自定义网络 3、创建自定义…

算法学习(四)将一颗二叉搜索树转排序的双向链表

描述 输入一棵二叉搜索树&#xff0c;将该二叉搜索树转换成一个排序的双向链表。如下图所示 数据范围&#xff1a;输入二叉树的节点数 0 \le n \le 10000≤n≤1000&#xff0c;二叉树中每个节点的值 0\le val \le 10000≤val≤1000 要求&#xff1a;空间复杂度O(1)O(1)&#x…

使用 Requests 库和 PHP 的下载

以下是一个使用 Requests 库和 PHP 的下载器程序&#xff0c;用于从 www.people.com.cn 下载音频。此程序使用了 https://www.duoip.cn/get_proxy 这段代码。 import requests from bs4 import BeautifulSoup import pafy import timedef get_proxy():url "https://www.…

Linux驱动基础篇(一)GPIO(上)LED驱动

文章目录 Linux驱动基础&#xff08;一&#xff09;GPIO&#xff08;上&#xff09;LED驱动一、开发环境准备1.安装交叉编译工具编译内核&#xff08;1&#xff09;安装交叉编译工具&#xff08;2&#xff09;修改Makefile指定编译器和架构&#xff08;3&#xff09;生成配置文…

《java核心卷Ⅰ》知识点总结(可作面试题)

&#x1f6eb; JDK和JRE傻傻分不清?&#x1f6eb; HelloWorld的输出都经历了啥&#xff1f;&#x1f6eb; Java的三个版本都是啥&#xff1f;&#x1f6eb; 关于main方法你都知道啥&#xff1f;main方法被声明为private会怎样&#xff1f;&#x1f6eb; 强制and自动类型转换都…

Unity解决:导出AndroidStudio工程 出现如下报错的解决方法

unity2019.4+ androidStudio2023.x+ 问题1: cvc-complex-type.2.4.a: 发现了以元素 base-extension 开头的无效内容。应以 {layoutlib} 之一开头。 解决:第一个Build.gradle更改如下 // GENERATED BY UNITY. REMOVE THIS COMMENT TO PREVENT OVERWRITING WHEN EXPORTING …

中文编程开发语言工具系统化教程初级1上线

中文编程系统化教程初级1 学习编程捷径&#xff1a;&#xff08;不论是正在学习编程的大学生&#xff0c;还是IT人士或者是编程爱好者&#xff0c;在学习编程的过程中用正确的学习方法 可以达到事半功倍的效果。对于初学者&#xff0c;可以通过下面的方法学习编程&#xff0c;…

用Flask快速生成报表

一、前言 《用Python快速生成报表之一》 我们介绍了用html-table快速生成表格数据报表&#xff0c;今天我们再介绍一下用Python Flask 快速开发报表&#xff0c;使用的是最古老的套页面方式。 二、Flask快速生成报表 Python有N多Web框架&#xff0c;最强大最出名的是Django&…