蓝桥杯每日真题 - 第14天

news/2024/11/20 5:32:15/

题目:(2022)

题目描述(13届 C&C++ B组A题)

 

解题思路:

  • 定义状态
    使用一个二维数组 dp[j][k] 来表示将数字 k 拆分为 j 个不同正整数的方案数。

  • 初始化
    初始状态设定为 dp[0][0] = 1,表示将数字 0 拆分为 0 个数有一种方式(即不选择任何数)。

  • 状态转移方程
    我们逐步遍历 1 到 2022 的所有正整数 i,并利用 j 表示当前所需的数字个数。

    • 如果选择当前数 i,则可以从 dp[j-1][k-i] 进行转移,将数 k 拆分为 j 个数的方案可以由数 k-i 拆分为 j-1 个数的方案转移而来。

    • 因此,状态转移方程为: dp[j][k]+=dp[j−1][k−i]dp[j][k] += dp[j-1][k-i]dp[j][k]+=dp[j−1][k−i]

    • 该公式表示,当前数值 k 的方案数等于在 j-1 个不同数构成 k-i 的方案数上加上 i

  • 边界条件
    由于拆分出的数需要互不相同,我们在外层循环中设定 j 从 10 到 1 逆序遍历,以确保每个数只被用一次。

  • 最终结果
    经过所有状态的更新后,dp[10][2022] 就代表了将 2022 拆分为 10 个互不相同的正整数的方案数。

代码实现(C语言):

#include <stdio.h>
#include <stdlib.h>long long dp[11][2032];int main() {dp[0][0] = 1; // 初始状态:0 可以被拆分为 0 个数的一种方式for (int i = 1; i <= 2022; i++) {for (int j = 10; j >= 1; j--) {for (int k = i; k <= 2022; k++) {dp[j][k] += dp[j-1][k-i];}}}printf("%lld\n", dp[10][2022]);return 0;
}

得到运行结果:

代码分析: 

  • dp[0][0] = 1:初始化,表示将 0 拆分成 0 个数有 1 种方案。

  • 外层循环 i 遍历 1 到 2022 的所有正整数。

  • 中层循环 j 表示当前所需的数个数,逆序从 10 到 1 遍历,保证每个数仅被用一次。

  • 内层循环 k 表示当前和的数值,从 i 到 2022。

  • 状态转移 dp[j][k] += dp[j-1][k-i],即数 k 的方案数可以由 j-1 个数构成的 k-i 的方案数转移而来。

难度分析

⭐️⭐️⭐️

总结

本题利用动态规划实现了从小到大的逐步转移,计算出将 2022 拆分成 10 个互不相同的正整数的方案数。动态规划的优点是避免了重复计算,提高了效率。最终结果储存在 dp[10][2022] 中,即为所求解。


http://www.ppmy.cn/news/1548419.html

相关文章

实用教程:如何无损修改MP4视频时长

如何在UltraEdit中搜索MP4文件中的“mvhd”关键字 引言 在视频编辑和分析领域&#xff0c;有时我们需要深入到视频文件的底层结构中去。UltraEdit&#xff08;UE&#xff09;和UEStudio作为强大的文本编辑器&#xff0c;允许我们以十六进制模式打开和搜索MP4文件。本文将指导…

鸿蒙生态开发以及技术栈介绍

​&#x1f308;个人主页&#xff1a;前端青山 &#x1f525;系列专栏&#xff1a;鸿蒙开发篇 &#x1f516;人终将被年少不可得之物困其一生 依旧青山,本期给大家带来鸿蒙开发篇专栏内容: 有没有可以2小时不用手机的&#xff1f; 打开电视用什么&#xff1f; 打开空调用什么&a…

React教程第二节之虚拟DOM与Diffing算法理解

1、什么是虚拟DOM 虚拟DOM 是javascript的一个对象&#xff0c;是内存中的一种数据结构&#xff0c;以树的形式存储UI的状态&#xff0c;树中的每个节点都代表着真实的DOM&#xff0c;用来描述我们希望在页面看到的 HTML结构&#xff1b; 现在的MVVM 框架&#xff0c;大多使用…

CSM32RV20:RISC-V核的低功耗MCU芯片,常用在智能门锁上

CSM32RV20是一款基于RISC-V核的低功耗MCU芯片。 内置RISC-V RV32IMAC内核&#xff08;2.6CoreMark/MHz&#xff09;&#xff1b; 蕞高32MHz工作频率&#xff1b; 内置4kB的SRAM&#xff1b; 内置8B的ALWAYS寄存器&#xff0c;能在掉电模式2下保存数据&#xff1b; 内置40kB的嵌…

区块链中的wasm合约是什么?

概述 让我们梳理一下WASM合约的概念和重要性…这涉及到区块链和智能合约的发展。 WASM(WebAssembly)本身是一种低级的类汇编语言&#xff0c;最初是为Web浏览器设计的。将它引入区块链领域是一个重要创新。 相比传统的智能合约(如Solidity)&#xff0c;WASM有很多优势&#…

stm32启动过程解析startup启动文件

1.STM32的启动过程模式 1.1 根据boot引脚决定三种启动模式 复位后&#xff0c;在 SYSCLK 的第四个上升沿锁存 BOOT 引脚的值。BOOT0 为专用引脚&#xff0c;而 BOOT1 则与 GPIO 引脚共用。一旦完成对 BOOT1 的采样&#xff0c;相应 GPIO 引脚即进入空闲状态&#xff0c;可用于…

泷羽sec-安全见闻(9)

安全见闻&#xff08;9&#xff09; 声明&#xff01; 学习视频来自B站up主 泷羽sec 有兴趣的师傅可以关注一下&#xff0c;如涉及侵权马上删除文章&#xff0c;笔记只是方便各位师傅的学习和探讨&#xff0c;文章所提到的网站以及内容&#xff0c;只做学习交流&#xff0c;其…

【Python】selenium安装+Microsoft Edge驱动器下载配置流程

文章目录 简介一、安装浏览器对应驱动1.1 查看浏览器当前版本1.2 下载驱动器1.3 配置环境1.3.1 补充——忘记python的解释器位置&#xff1f; 二、selenium安装及验证配置1.安装selenium2.验证配置2.2.1 补充——selenium打开浏览器自动退出&#xff1f; 总结 简介 本文主要介…