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

这篇具有很好参考价值的文章主要介绍了蓝桥杯(路径 动态规划 C++)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

蓝桥杯(路径 动态规划 C++),蓝桥杯,蓝桥杯,c++,职场和发展

 思路:

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

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

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

4、最后输出f[2021]就是第一个点到第2021个点的最短距离。文章来源地址https://www.toymoban.com/news/detail-723151.html

#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);
			else
				f[j] = min(f[j], f[i] + i * j / gcd(i, j));
		}
	cout << f[2021] << endl;
}

到了这里,关于蓝桥杯(路径 动态规划 C++)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 动态规划:路径和子数组问题(C++)

    1.不同路径(中等) 链接:不同路径 题目描述 做题步骤 状态表示 尝试 定义状态表示为到达[m, n]位置的路径数 。 状态转移方程 通过上述分析,可知状态转移方程为: dp[i][j] = dp[i - 1][j] + dp[i][j - 1] 。 初始化 填表顺序 保证填当前状态时,所需状态已经计算过,从起点出发,

    2024年02月10日
    浏览(30)
  • C++ 动态规划 状态压缩DP 最短Hamilton路径

    给定一张 n 个点的带权无向图,点从 0∼n−1 标号,求起点 0 到终点 n−1 的最短 Hamilton 路径。 Hamilton 路径的定义是从 0 到 n−1 不重不漏地经过每个点恰好一次。 输入格式 第一行输入整数 n 。 接下来 n 行每行 n 个整数,其中第 i 行第 j 个整数表示点 i 到 j 的距离(记为 a[

    2024年02月19日
    浏览(40)
  • 蓝桥杯丨动态规划

    做你想做的,错的算我的 这里是Want595,欢迎光临我的世界 ~   目录 前言  一、斐波那契式 通项公式:f(n)=f(n-1)+f(n-2)  举例说明 爬楼梯  骨牌铺方格  一只小蜜蜂 二、背包问题 通项公式:f(i,j)=max(f(i-1,j),f(i-1(或i),j-w(i))+v(i))  举例说明  0-1背包问题  完全背包问题  矿工

    2024年02月11日
    浏览(36)
  • 【蓝桥杯-筑基篇】动态规划

    🍓系列专栏:蓝桥杯 🍉个人主页:个人主页 目录 1.最大连续子段和 2.LCS 最大公共子序列 3.LIS 最长上升子序列 4.数塔 5.最大子矩阵和 6.背包问题 ①01背包问题 ②完全背包 这段代码是一个求最大子数组和的算法,使用的是动态规划的思想。下面是代码的解释: 首先定义了一个

    2023年04月24日
    浏览(72)
  • 蓝桥杯动态规划基础篇(一)

    动态规划(Dynamic Programming,DP)是运筹学的一个分支,是求解决策过程最优化的过程。20世纪50年代初,美国数学家贝尔曼(R.Bellman)等人在研究多阶段决策过程的优化问题时,提出了著名的最优化原理,从而创立了动态规划。动态规划的应用极其广泛,包括工程技术、经济、

    2024年02月03日
    浏览(38)
  • 【蓝桥杯/动态规划】数的计算

    题目描述 输入一个自然数 n (n≤1000)n (n leq 1000) n   ( n ≤ 1 0 0 0 ) ,我们对此自然数按照如下方法进行处理: 不作任何处理; 在它的左边加上一个自然数,但该自然数不能超过原数的一半; 加上数后,继续按此规则进行处理,直到不能再加自然数为止。 问总共可以产生多少个数。

    2024年02月01日
    浏览(49)
  • 蓝桥杯-动态规划-子数组问题

    目录 一、乘积最大数组 二、乘积为正数的最长子数组长度 三、等差数列划分 四、最长湍流子数组 心得: 最重要的还是状态表示,我们需要根据题的意思,来分析出不同的题,不同的情况,来分析需要多少个状态 乘积最大数组 1.状态表示 dp[i]:到达i位置的最大乘积子数组。

    2024年02月05日
    浏览(36)
  • 蓝桥杯-回路计数(状态压缩、动态规划)

    蓝桥学院由 21 21 21 栋教学楼组成,教学楼编号 11 11 11 ​​ 到 21 21 21 ​​。对于两栋教学楼 a a a 和 b b b ​,当 a a a 和 b b b 互质时, a a a 和 b b b 之间有一条走廊直接相连,两个方向皆可通行,否则没有直接连接的走廊。 小蓝现在在第一栋教学楼,他想要访问每栋教学楼正

    2024年02月08日
    浏览(60)
  • 蓝桥:保险箱(Python,动态规划)

    小蓝有一个保险箱,保险箱上共有 n 位数字。小蓝可以任意调整保险箱上的每个数字,每一次操作可以将其中一位增加 1 或减少 1。当某位原本为 9 或 0 时可能会向前(左边)进位/退位,当最高位(左边第一位)上的数字变化时向前的进位或退位忽略。 例如: 00000 的第 5 位减

    2024年04月09日
    浏览(92)
  • JAVA蓝桥杯备考---6.动态规划(一)

    动态规划简称 DP,通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。动态规划常常适用于有重叠子问题和最优子结构性质的问题。 简单来说,动态规划其实就是,给定一个问题,我们把它拆成一个个子问题,直到子问题可以直接解决然后呢,把子问题答案保

    2024年02月19日
    浏览(33)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包