当前位置：首页 > news >正文

蓝桥杯备考：多米诺骨牌

news 来源：原创 2025/7/13 7:46:10

这道题要求上下方格子和之差要最小，其实就是算每个上下格子的差求和的最小值

这道题其实是动态规划01背包问题

我们直接按步骤做吧

step1:定义状态表示f[i][j]表示从1到i个编号的差值里选出刚好j个数的最小操作次数

step2:推导状态转移方程

如图这就是我们的状态转移方程，由于它既是需要上面的左边区域也是需要上面的右边区域，so不能进行空间优化了

step3：初始化

把f[0][0]初始化为0，其他的全初始化为无穷大

step4:结果怎么看，

我们发现，最大的情况就是上面全部都是6，下面全是1，这时候我们的差值的和就是5000

我们设x遍历1到5000，比较x和-x，如果有答案，取最小的数

但是有一点就是，我们的和是可能是负数的，那时候我们怎么存？我们可以把dp表所有格子整体右移动m单位

下面是我们实现的代码

#include <iostream>
#include <cstring>
using namespace std;
const int N = 1010;
const int M = 1e4+10;
const int INF = 0x3f3f3f3f;
int n;
int f[N][M];
int a[N];
int main()
{cin >> n;for(int i = 1;i<=n;i++){int x,y;cin >> x >> y;a[i] = x-y;}memset(f,0x3f,sizeof(f));int m = 5000;f[0][0+m] = 0;for(int i = 1;i<=n;i++){for(int j = -m;j<=m;j++){f[i][j+m] = min(f[i-1][j-a[i]+m],f[i-1][j+a[i]+m]+1);}}int ret = INF;for(int j = 0;j<=m;j++){ret = min(f[n][j+m],f[n][-j+m]);if(ret!=INF) break;}cout << ret;return 0;
}

蓝桥杯备考：多米诺骨牌

这道题要求上下方格子和之差要最小，其实就是算每个上下格子的差求和的最小值这道题其实是动态规划01背包问题我们直接按步骤做吧 step1:定义状态表示f[i][j]表示从1到i个编号的差值里选出刚好j个数的最小操作次数 step2:推导状态转移方程如图这就是我们的状态…...

编程日记 2025/7/13 7:46:10

C++：allocator类(动态数组续）

1.为什么需要 allocator？ 在 C 中，动态内存管理通常通过 new 和 delete 完成： int* p new int; // 分配内存构造对象 delete p; // 析构对象释放内存但 new 和 delete 有两个问题： 耦合性：将内…...

编程日记 2025/7/13 7:12:19

Go语言手动内存对齐的四大场景与实践指南

Go语言手动内存对齐的四大场景与实践指南引言：Go的内存对齐机制 Go语言通过编译器自动处理内存对齐问题，开发者通常无需关心底层细节。然而，在特定场景下，手动干预内存对齐是避免程序崩溃或数据错乱的必要操作。本文将深入探讨G…...

编程日记 2025/7/12 6:14:00

libva基础

Libva（Lib Video Acceleration）是一个开源的库，实现了 **VA-API**（Video Acceleration API），旨在为视频处理提供跨平台的硬件加速支持。 1、核心功能与作用硬件加速抽象层：Libva 作为中间层&…...

编程日记 2025/7/2 7:04:07

如何在 AI 搜索引擎（GEO）霸屏曝光，快速提升知名度？

虽然大多数人仍然使用 Google 来寻找答案，但正在发生快速转变。ChatGPT、Copilot、Perplexity 和 DeepSeek 等 LLM 已成为主流。这主要是因为每个都有自己的免费和公共版本，并且总是有重大的质量改进。许多人每天都使用这些工具来提问和搜索互联网&…...

编程日记 2025/7/9 14:27:32

Java入门知识总结——章节（二）

ps：本章主要讲数组、二维数组、变量一、数组数组是一个数据容器，可用来存储一批同类型的数据 🔑：注意类也可以是一个类的数组 public class Main {public static class Student {String name;int age; // 移除 unsignedint…...

编程日记 2025/7/5 1:21:35

Python 序列构成的数组(元组不仅仅是不可变的列表)

元组不仅仅是不可变的列表有些 Python 入门教程把元组称为“不可变列表”，然而这并没有完全概括元组的特点。除了用作不可变的列表，它还可以用于没有字段名的记录。鉴于后者常常被忽略，我们先来看看元组作为记录的功用。元组和记录元…...

编程日记 2025/7/12 6:05:37

双指针法 c 语言实现 void moveZeroes(int* nums, int numsSize) {int dest,cur; //创建临时指针和目标指针destcur0;//出初始化while(cur<numsSize)//遍历{if(nums[cur]!0){swap(&nums[cur],&nums[dest]);cur;dest;}else{cur;}}} 思路是建立两个指针&#xff0…...

编程日记 2025/7/10 14:01:23

wait函数等待多个子进程

父进程等待多个子进程时可以使用 wait() 函数，但有一些要点需要注意，下面为你详细介绍相关内容。可以使用 wait() 函数等待多个子进程的原理 wait() 函数会让调用它的父进程暂停执行，直到它的某个子进程结束，然后返回结束子进程…...

编程日记 2025/7/11 16:52:42

数据湖的数据存储与管理策略：构建高效的数据管理框架

数据湖的数据存储与管理策略：构建高效的数据管理框架在大数据时代，数据湖作为存储和管理海量数据的关键技术，已经成为众多企业数字化转型的重要组成部分。数据湖的核心优势在于其能够支持结构化、半结构化和非结构化数据的存储，然而，随着数据量的增加和复杂度的提升，如…...

编程日记 2025/7/8 7:45:37

Linux进程管理之进程的概念、进程列表和详细的查看、进程各状态的含义

进程的概念进程是程序执行的实例，在Linux中，每个进程都有一个唯一的PID（进程ID）。查看当前系统中有哪些进程在Linux系统中，查看当前运行的进程可以使用几个常用命令： ps - 显示当前进程的快照。常用选…...

编程日记 2025/7/4 0:29:57

3万字长文详解Android AIDL 接口设计

目录第一章：AIDL 概述 1.1 什么是 AIDL？定义与核心作用 1.2 AIDL 的典型使用场景第二章：AIDL 语法规则 2.1 支持的数据类型：从基础到高级 2.2 接口声明：写好通信的 “剧本” 2.3 方向标记：数据流向的 “交通灯” 第三章：AIDL 文件编写 3.1 创建 AIDL 文件：从…...

编程日记 2025/7/9 10:50:13

HFSS 使用入门

资源下载资源： https://download.csdn.net/download/wangjun_huster/90547193 下载破解： https://download.csdn.net/download/wangjun_huster/90547551 安装 https://www.bilibili.com/list/ml3403866295?oid925751664&bvidBV1CT4y1u7LB 入门…...

编程日记 2025/7/12 10:32:23

精心整理-2024最新网络安全-信息安全全套资料（学习路线、教程笔记、工具软件、面试文档）.zip

2024最新网络安全-信息安全全套资料（学习路线、教程笔记、工具软件、面试文档），视频教程文档资料共55GB。一、网络安全-信息安全学习路线 0、网络安全-信息安全思维导图.jpg 1、网络安全大师课 V2024.pdf 2、网络安全行业白皮书.pdf 3、网络…...

编程日记 2025/6/28 1:36:31

RAG基建之PDF解析的“流水线”魔法之旅

将PDF文件和扫描图像等非结构化文档转换为结构化或半结构化格式是人工智能的关键部分。然而，由于PDF的复杂性和PDF解析任务的复杂性，这一过程显得神秘莫测。在RAG（Retrieval-Augmented Generation）基建之PDF解析的“魔法”与“陷阱”中，我们介绍了PDF解析的主要任务，对现…...

编程日记 2025/7/11 15:48:29

leetcode刷题日记——跳跃游戏

[ 题目描述 ]： [ 思路 ]： 题目要求在给出的每次可移动最大步数中选择一个移动步数，如果有一种选择能达到终点就返回true，如果没有一种选择能够达到终点就返回false因为每次给出的最大步数不同，步数越大，…...

编程日记 2025/7/9 22:09:20

Scala 数组

Scala 数组引言 Scala 作为一门多范式编程语言，融合了面向对象和函数式编程的特点。数组是编程语言中非常基础和常见的数据结构，在 Scala 中也不例外。本文将详细介绍 Scala 中的数组，包括其定义、操作以及在实际开发中的应用。 Scala 数…...

编程日记 2025/7/10 17:48:36

基于华为设备技术的端口类型详解

以下是基于华为设备技术网页的端口类型详解（截至2025年3月）： 一、Access端口定义：仅允许单个VLAN通过，用于连接终端设备（如PC、打印机） 处理流程： 接收帧：未带标签…...

编程日记 2025/7/10 19:51:01

使用 Go 和 Gin 实现高可用负载均衡代理服务器

前言在现代分布式系统中，负载均衡是保障服务高可用性和性能的核心技术。本文将基于 Go 语言和 Gin 框架实现一个支持动态路由、健康检查、会话保持等特性的企业级负载均衡代理服务器，并提供完整的压力测试方案和优化建议。通过本方案实现的负载均衡代理具备以下优势：单…...

编程日记 2025/7/10 4:26:23

零基础驯服GitHub Pages

各位互联网流浪汉、赛博吉普赛人、以及不小心点进来的产品经理们！今天我们要用程序员的方式搞点大事情——不写代码、不买服务器、不氪金，免费拥有一个能吹牛的个人网站！准备好你的键盘和表情包收藏夹，我们的奇幻漂流开始了&#…...

编程日记 2025/7/7 22:52:19

OpenBMC：BmcWeb 生效路由5 优化trie

OpenBMC：BmcWeb 生效路由4 将路由添加到Trie中-CSDN博客在url被添加到trie中后，validate的最后一步是优化trie void validate() {for (std::unique_ptr<BaseRule>& rule : allRules){if (rule){std::unique_ptr<BaseRule> upgraded = rule->upgrade();if…...

编程日记 2025/7/4 20:03:51

买卖股票的最佳时机（121）

121. 买卖股票的最佳时机 - 力扣（LeetCode） 解法： class Solution { public:int maxProfit(vector<int>& prices) {int cur_min prices[0];int max_profit 0;for (int i 1; i < prices.size(); i) {if (prices[i] > cur…...

编程日记 2025/7/2 22:58:03

强大的AI网站推荐（第四集）—— Gamma

网站：Gamma 号称：展示创意的新媒介博主评价：快速展示创意，重点是展示，在几秒钟内快速生成幻灯片、网站、文档等内容推荐指数：🌟🌟🌟🌟🌟&#x…...

编程日记 2025/7/2 7:06:41

Business Trip and Business Travel

Business Trip and Business Travel References Background I would like to introduce the background. Dave is going on a business trip, but he’s very busy, so he needs Leo’s help to buy the plane ticket. Panda is an agent of China Eastern /ˈiːstərn/ Airl…...

编程日记 2025/7/9 1:35:49

为pip设置国内镜像源

pip设置国内镜像源在Python中使用pip安装软件包时，通常我们会遇到网络问题，尤其是在中国大陆地区。为了解决这个问题我们可以使用一些国内提供的镜像源。下面以清华大学的镜像源为例进行使用说明。方法一：临时使用在命令行中&#xff0…...

编程日记 2025/7/10 21:22:51

MySQL查询成本计算

对于如上SQL，只是因为查询字段不同，最终执行时选择的索引就不同，那么MySQL是如何决定选择使用哪个索引呢？ 答案是MySQL会进行成本计算，对于各个场景查询进行成本预估，最终选择最优。我们可以使用trace工具…...

编程日记 2025/7/10 21:25:05

使用 rsync 进行服务器文件同步与优化

使用 Rsync 工具在两台 Linux 服务器之间同步文件 Rsync 是一种高效的文件同步工具，它可以在本地或远程服务器之间同步文件和目录。Rsync 通过仅传输文件的变化部分来减少数据传输量，因此特别适合用于定期备份或同步大量数据。本文将详细介绍如何将 A 服…...

编程日记 2025/7/10 20:22:33

java面向对象从入门到入土

面向对象进阶（写程序的套路）面向：拿，找对象：能干活的东西面向对象编程：拿东西过来做对应的事情（写程序的套路）面向：拿，找对象：能干活的东西面向对象编程：拿东西过来做对应的事情重点学习：学习已有对象并使用，学习如何自己设计对象并使用设计对…...

编程日记 2025/7/12 1:43:37

Redis设计与实现-哨兵

哨兵模式 1、启动并初始化sentinel1.1 初始化服务器1.2 使用Sentinel代码1.3 初始化sentinel状态1.4 初始化sentinel状态的master属性1.5 创建连向主服务器的网络连接 2、获取主服务器信息3、获取从服务器的信息4、向主从服务器发送信息5、接受主从服务器的频道信息6、检测主观…...

编程日记 2025/7/12 14:25:43

vscode 打开工程看不到文件目录

vscode 打开工程看不到文件目录 View->Explorer 快捷键：CtrlShiftE...

编程日记 2025/6/28 1:57:36

[c++项目]基于微服务的聊天室服务端测试

项目概述本测试报告针对基于C实现的微服务架构聊天室服务端进行全面测试。系统主要包含以下微服务： 用户认证服务（Auth Service）消息处理服务（Message Service）在线状态服务（Presence Service&#xff0…...

编程日记 2025/7/8 16:16:39

Java面试黄金宝典16

1. 各种排序算法的时间复杂度和空间复杂度冒泡排序定义： 冒泡排序是一种简单的排序算法。它重复地走访过要排序的数列，一次比较两个元素，如果它们的顺序错误就把它们交换过来。走访数列的工作是重复地进行直到没有再需要交换，…...

编程日记 2025/6/28 1:36:46

pytorch中dataloader自定义数据集

前言在深度学习中我们需要使用自己的数据集做训练，因此需要将自定义的数据和标签加载到pytorch里面的dataloader里，也就是自实现一个dataloader。数据集处理以花卉识别项目为例，我们分别做出图片的训练集和测试集，训练集的标…...

编程日记 2025/7/11 8:10:12

LabVIEW 燃气轮机气路故障诊断

在船用燃气轮机气路故障诊断领域，LabVIEW 软件以其独特的功能和优势，成为构建高效、精准诊断系统的关键技术支撑。它全面覆盖硬件在环仿真平台的各个环节，从硬件连接、数据交互到系统功能实现，都发挥着不可替代的作用，…...

编程日记 2025/7/12 4:30:56

[项目]基于FreeRTOS的STM32四轴飞行器: 十六.激光测距定高功能

基于FreeRTOS的STM32四轴飞行器: 十六.激光测距定高功能一.芯片介绍二.配置CubeMX三.激光测距芯片驱动编写四.定高PID的计算五.定高PID作用到电机上一.芯片介绍激光测高芯片在飞控板下侧： 原理图如下： 型号为：VL53LX1，为国产…...

编程日记 2025/7/11 11:53:05

HTML跑酷

先看效果再上代码 <!DOCTYPE html> <html> <head><title>火柴人跑酷</title><style>body {margin: 0;overflow: hidden;background: #87CEEB;}#gameCanvas {background: linear-gradient(to bottom, #87CEEB 0%, #87CEEB 50%, #228B22 …...

编程日记 2025/7/9 8:20:35

C++Primer学习（14.1 基本概念）

当运算符作用于类类型的运算对象时，可以通过运算符重载重新定义该运算符的含义。明智地使用运算符重载能令我们的程序更易于编写和阅读。举个例子，因为在Sales_item类中定义了输入、输出和加法运算符，所以可以通过下述形式输出两个Sales_item…...

编程日记 2025/7/10 4:16:43

【Goalng】第九弹-----文件操作、JSON处理

🎁个人主页：星云爱编程 🔍所属专栏：【Go】 🎉欢迎大家点赞👍评论📝收藏⭐文章长风破浪会有时，直挂云帆济沧海目录 1.文件操作 1.1文件介绍 1.2.文件流 1.3.打开和关闭文件 1…...

编程日记 2025/7/4 19:31:24

锐评｜希捷NVMe闪存+磁盘混合存储阵列

近日，希捷在英伟达GTC 2025会议上展示了NVMe混合闪存/磁盘阵列技术。这个混合存储阵列确实在当前AI数据存储困境中撕开了一道新口子，但远称不上完美，优缺点都极为鲜明。从优点来看，希捷切中了大多数企业的痛点。AI领域数据量呈爆…...

编程日记 2025/7/9 8:30:25

如何缩短研发周期，降低研发成本？全星APQP软件为您提供解决方案

如何缩短研发周期，降低研发成本？全星APQP软件为您提供解决方案一、系统概述全星研发管理APQP软件系统是一款专为产品研发和质量管控打造的智能化平台，旨在帮助企业高效推进APQP（先期产品质量策划）流程&#xff0c…...

编程日记 2025/7/9 14:10:51

Centos7安装cat美化工具lolcat

Centos7安装cat美化工具lolcat Centos7安装lolcat使用ruby安装lolcat配置cat系统别名结果验证 Centos7安装lolcat lolcat ：一个在Linux 终端中输出彩虹特效的命令行工具使用ruby安装lolcat # 安装ruby和zip yum install -y ruby# 查看ruby版本 ruby --version# …...

编程日记 2025/7/9 1:35:49

bluecode-20240913_1_数据解码

时间限制：C/C 1000MS，其他语言 2000MS 内存限制：C/C 256MB，其他语言 512MB 难度：困难数据解码指定有一段经过编码的二进制数据，数据由0个或多个"编码单元"组成。"编码单元"的编码方式…...

编程日记 2025/7/10 14:30:21

【＜二＞丹方改良：Spring 时代的 JavaWeb】之 Spring Boot 中的缓存技术：使用 Redis 提升性能

<前文回顾> 点击此处查看合集 https://blog.csdn.net/foyodesigner/category_12907601.html?fromshareblogcolumn&sharetypeblogcolumn&sharerId12907601&sharereferPC&sharesourceFoyoDesigner&sharefromfrom_link <今日更新> 一、开篇整…...

编程日记 2025/7/8 22:58:10

典范硬币系统（Canonical Coin System）→ 贪心算法

【典范硬币系统】 ● 典范硬币系统（Canonical Coin System）是指使用贪心算法总能得到最少硬币数量解‌的货币面值组合‌。 ● 给定一个硬币系统 ，若使其为典范硬币系统，则要求其各相邻面值比例 ，及各开区间内各金额…...

编程日记 2025/7/10 19:25:15

hbuilderx打包iOS上传苹果商店的最简流程

无需Mac电脑，无需安装xcode和transporter，其实使用hbuilderx开发的ios软件，也可以上架到苹果的app store商店的。只需要有苹果开发者中心的苹果开发者账号就行了。假如你还在了解上架阶段，还没打包，也还没有创建任…...

编程日记 2025/7/9 8:30:42

DeepSeek详解：探索下一代语言模型

文章目录前言一、什么是DeepSeek二、DeepSeek核心技术2.1 Transformer架构2.1.1 自注意力机制 (Self-Attention Mechanism)(a) 核心思想(b) 计算过程(c) 代码实现 2.1.2 多头注意力 (Multi-Head Attention)(a) 核心思想(b) 工作原理(c) 数学描述(d) 代码实现 2.1.3 位置编码 (…...

编程日记 2025/7/12 11:37:56

python的内存管理

目录 1. 引用计数 2. 垃圾收集（GC） python的内存管理主要是引用计数和垃圾回收器来进行内存管理 1. 引用计数每个 Python 对象都有一个引用计数，当引用计数为零时，对象的内存会被释放。 import sysa [] # 创建一个空列表对…...

编程日记 2025/7/4 4:33:37

【STL】list

l i s t list list 是 C C C 标准模板库（ S T L STL STL）中的一个序列容器（ S e q u e n c e C o n t a i n e r Sequence\ Container Sequence Container），它允许在容器的任意位置快速插入和删除元素，是一…...

编程日记 2025/7/5 0:19:37

证券公司主要业务分析及当前佣金最低免五情况探讨

我是StockMasterX，今日想分析证券公司主要业务，并探讨当前佣金最低且免五的证券公司情况，此议题具有一定研究价值，我从事股票交易多年，与证券公司互动频繁，前日晚间饮茶之际，浏览手机时对此深思…...

编程日记 2025/7/8 22:43:59

C++ 变量的声明与定义分离式编译与静态类型（十六）

1. 声明与定义的区别声明（declaration）：向编译器表明某个变量（或其他实体）的类型与名字，使它在后续的编译过程中可见或可用。定义（definition）：除了声明变量的名字和类…...

编程日记 2025/7/10 13:27:51

相关文章：