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

经典算法石子合并问题

news 来源：原创 2025/5/7 4:26:16

石子合并问题

问题描述

在一个园形操场的四周摆放N堆石子,现要将石子有次序地合并成一堆.规定每次只能选相邻的2堆合并成新的一堆，并将新的一堆的石子数，记为该次合并的得分。试设计出一个算法,计算出将N堆石子合并成1堆最大得分和最小得分。

输入描述

第一行一个整数(n)1 <= n <= 100，接下来一行n个整数，表示每堆石子的个数。

输出描述

输出第一行最小得分，第二行最大得分。

输入示例

4
4 4 5 9

输出示例

43
54

输入示例

7
6 4 36 4 7 14 25

输出示例

237
430

c++代码

#include<bits/stdc++.h>using namespace std;int main() {int n, max_val = INT_MIN, min_val = INT_MAX;cin >> n;vector<int> arr(2 * n + 1);for (int i = 1; i <= n; i++) cin >> arr[i];for (int i = n + 1; i <= 2 * n; i++) arr[i] = arr[i - n];for (int i = 1; i <= 2 * n; i++) arr[i] += arr[i - 1];vector<vector<int>> dp(2 * n + 1, vector<int>(2 * n + 1, 0));for (int len = 2; len <= 2 * n; len++) {for (int i = 1; i + len - 1 <= 2 * n; i++) {for (int j = i; j < i + len - 1; j++) {dp[i][i + len - 1] = max(dp[i][i + len - 1], dp[i][j] + dp[j + 1][i + len - 1] + arr[i + len - 1] - arr[i - 1]);}}}for (int i = 1; i <= n; i++) max_val = max(max_val, dp[i][i + n - 1]);dp = vector<vector<int>>(2 * n + 1, vector<int>(2 * n + 1, INT_MAX));for (int i = 1; i <= 2 * n; i++) dp[i][i] = 0;for (int len = 2; len <= 2 * n; len++) {for (int i = 1; i + len - 1 <= 2 * n; i++) {for (int j = i; j < i + len - 1; j++) {dp[i][i + len - 1] = min(dp[i][i + len - 1], dp[i][j] + dp[j + 1][i + len - 1] + arr[i + len - 1] - arr[i - 1]);}}}for (int i = 1; i <= n; i++) min_val = min(min_val, dp[i][i + n - 1]);cout << min_val << endl << max_val;return 0;
}//by wqs

链形的石子合并

这个题目是环形的，也就是，第一个和最后一个石子可以合并，我们来考虑链形的石子合并怎么写，再推广到环形的。

由于最大得分和最小得分的思路是一样的，我们为了减少代码的冗余度，只说最大得分的算法。

链形石子合并 c++代码()

#include<bits/stdc++.h>using namespace std;int main() {int n;cin >> n;vector<int> arr(n + 1);for (int i = 1; i <= n; i++) cin >> arr[i], arr[i] += arr[i - 1];vector<vector<int>> dp(n + 1, vector<int>(n + 1));for (int len = 1; len <= n; len++) {for (int i = 1; i + len - 1 <= n; i++) {for (int j = i; j < i + len - 1; j++) {dp[i][i + len - 1] = max(dp[i][i + len - 1], dp[i][j] + dp[j + 1][i + len - 1] + arr[i + len - 1] - arr[i - 1]);}}}cout << dp[1][n];return 0;
}

我们定义dp[i][j]表示从第i堆石子到第j堆沙子的最大得分。
我们假设i~k堆沙子合并好了,k + 1 ~ j堆沙子也合并好了
我们现在要尝试合并i~k堆沙子和k + 1 ~ j堆沙子，并计算得分是多少。
实际上得分等于dp[i][k] + dp[k + 1][j] + (i ~ j的元素的和)
dp[i][k]是i~k堆沙子累计的得分。i ~ k合并后的新沙子的值为 (i ~ k的和)
dp[k + 1][j]是k + 1 ~ j堆沙子的得分。k + 1 ~ j合并后的新沙子的值为 (k + 1 ~ j的和)
我们还要把两堆沙子合并。新沙子合并后得分为(i ~ k的和) + (k + 1 ~ j的和) = (i ~ j的元素的和)。
所以最大得分等于dp[i][k] + dp[k + 1][j] + (i ~ j的元素的和)我们要保证合并第第i堆石子到第j堆沙子前dp[i][k]和 dp[k + 1][j]的值已经知道了
也就是要先算长度短的区间状态，再算长度长的区间状态
for (int len = 1; len <= n; len++) {//第一个for循环枚举区间长度，先算长度小的区间for (int i = 1; i + len - 1 <= n; i++) {//第二个for循环枚举左端点，由左端点和区间长度算出右端点为i + len - 1for (int j = i; j < i + len - 1; j++) {//第三个for循环枚举k,用前缀和数组快速求区间和dp[i][i + len - 1] = max(dp[i][i + len - 1], dp[i][j] + dp[j + 1][i + len - 1] + arr[i + len - 1] - arr[i - 1]);}}
}

环形的石子合并

由于最大得分和最小得分的思路是一样的，我们为了减少代码的冗余度，只说最大得分的算法。

c++代码

#include<bits/stdc++.h>using namespace std;int main() {int n, max_val = INT_MIN;cin >> n;vector<int> arr(2 * n + 1);for (int i = 1; i <= n; i++) cin >> arr[i];for (int i = n + 1; i <= 2 * n; i++) arr[i] = arr[i - n];for (int i = 1; i <= 2 * n; i++) arr[i] += arr[i - 1];vector<vector<int>> dp(2 * n + 1, vector<int>(2 * n + 1, 0));for (int len = 2; len <= 2 * n; len++) {for (int i = 1; i + len - 1 <= 2 * n; i++) {for (int j = i; j < i + len - 1; j++) {dp[i][i + len - 1] = max(dp[i][i + len - 1], dp[i][j] + dp[j + 1][i + len - 1] + arr[i + len - 1] - arr[i - 1]);}}}for (int i = 1; i <= n; i++) max_val = max(max_val, dp[i][i + n - 1]);cout << max_val;return 0;
}

环形石子合并我们要采用化圈成线的思路。

具体来说，看样例

4 4 5 9

我们把数组拷贝一次变成

4 4 5 9 4 4 5 9

考虑4 4 5 9链形合并最大值

考虑4 5 9 4链形合并最大值

考虑5 9 4 4链形合并最大是

考虑9 4 4 5链形合并最大值

这四个最大值里面选择一个最大的就是环形最大值。

环形石子合并算法正确性证明

之所以这样做是对的，是因为n次的链形合并穷尽了环形合并的所有可能。

例如4 4 5 9，4和9环形合并变成13 4 5对应9 4 4 5，9和4链形合并13 4 5。

经典算法石子合并问题

石子合并问题问题描述在一个园形操场的四周摆放N堆石子,现要将石子有次序地合并成一堆.规定每次只能选相邻的2堆合并成新的一堆，并将新的一堆的石子数，记为该次合并的得分。试设计出一个算法,计算出将N堆石子合并成1堆最大得分和最小得分。输入描述…...

编程日记 2025/5/7 4:26:16

2025A卷华为OD机试真题-数组二叉树(C++/Java/Python)-100分

2025华为OD机试题库-(2025A卷+E卷+D卷)-(JAVA、Python、C++) 目录题目描述输入描述输出描述示例 1 示例 2 解题思路代码 c++ java python 题目描述二叉树也可以用数组来存储，给定一个数组，树的根节点的值储存在下标1，对于储存在下标n的节点，他的左子节点…...

编程日记 2025/5/3 19:04:27

NHANES指标推荐：TyG指数

文章题目：Association between the Triglyceride-glucose index and fragility fractures among US adults: insights from NHANES DOI：10.1186/s13098-025-01669-w 中文标题：美国成年人甘油三酯-葡萄糖指数与脆性骨折之间的关联：…...

编程日记 2025/5/3 18:53:13

文件操作--文件下载读取漏洞

本文主要内容文件下载产生任意语言代码下载功能函数检测白盒代码审计黑盒漏扫工具、公开漏洞、手工看参数值及功能点（资源下载） 利用常见文件后台首页日志等可见文件敏感文件数据库配置文件、各种接口文件、密匙…...

编程日记 2025/5/3 18:50:07

文章题目：The nonlinear association of ratio of total cholesterol to high density lipoprotein with cognition ability: evidence from a community cohort in China DOI：10.3389/fnut.2025.1525348 中文标题：总胆固醇与高密度脂蛋白比值…...

编程日记 2025/5/3 18:50:06

Linux-常用监控工具

以下是对 Linux 系统中常用监控工具（netstat、ss、dmesg）的系统性介绍，涵盖其核心功能、典型用法及实际应用场景，帮助您分析系统状态和内核参数调整后的效果： 1. netstat -s：网络协议栈统计监控功能 net…...

编程日记 2025/5/7 4:23:47

【HarmonyOS Next】地图使用详解（三）标点定位问题

背景在使用geoLocationManager的getCurrentLocation方法获得的用户定位经纬度的坐标系为 WGS84 ，但是mapkit使用的是GCJ02坐标系。因此，我们在使用获取用户经纬度然后直接生成标记时，会出现坐标偏移问题。如下： 解决方案使用…...

编程日记 2025/5/3 18:44:57

Linux运维中常用的磁盘监控方式

在Linux运维中，磁盘监控是一项关键任务，因为它能帮助我们预防磁盘空间不足或性能问题导致的服务中断或数据丢失。让我们来看看有哪些常用的磁盘监控方法吧！ 1. 查看磁盘使用情况（df命令） df命令用于显示文件系统的…...

编程日记 2025/5/3 18:42:54

前端面经-VUE3篇--vue3基础知识（二）计算属性(computed)、监听属性（Watch）

一、计算属性(computed) 计算属性（Computed Properties）是 Vue 中一种特殊的响应式数据，它能基于已有的响应式数据动态计算出新的数据。计算属性有以下特性： 自动缓存：只有当它依赖的响应式数据发生变化时&#xff…...

编程日记 2025/5/3 18:40:51

双向链表详解

一、双向链表介绍二、实现双向链表 1.定义双向链表的结构 2.双向链表的初始化 3.双向链表的尾插 4.双向链表的头插 5.双向链表的打印 6.双向链表的尾删 7.双向链表的头删 8.查找指定位置的数据 9.在指定位置之后插入数据 10.删除指定位置的数据 11.链表的销毁三、…...

编程日记 2025/5/3 18:39:49

基于SpringBoot+Vue实现的电影推荐平台功能一

一、前言介绍： 1.1 项目摘要 2023年全球流媒体用户突破15亿，用户面临海量内容选择困难，传统推荐方式存在信息过载、推荐精准度低等问题。传统推荐系统存在响应延迟高（平均>2s）。随着互联网的快速发展，…...

编程日记 2025/5/3 18:37:45

预订接口优化：使用本地消息表保证订单生成、库存扣减的一致性

🎯 本文介绍了一种优化预订接口的方法，通过引入本地消息表解决分布式事务中的最终一致性问题。原先的实现是在一个事务中同时扣减库存和创建订单，容易因网络不稳定导致数据不一致。改进后的方法将业务操作和消息发送封装在本地事务中&#xf…...

编程日记 2025/5/3 18:34:42

深度学习与 PyTorch 基础

笔记 1 深度学习简介 1.1 深度学习概念深度学习是机器学习的一类算法, 以人工神经网络为结构, 可以实现自动提取特征深度学习核心思想是人工神经网络为结构, 自动提取特征 1.2 深度学习特点自动提取特征解释性差大量数据和高性能计算能力非线性转换(引入非线性因…...

编程日记 2025/5/6 23:12:00

libevent库详解：高性能异步IO的利器

目录一、libevent 简介主要特点： 二、事件模型原理 1. event_base 2. event 3. evconnlistener（TCP监听器） 4. bufferevent 简化流程如下： 三、libevent 使用示例 1. 创建事件主循环 2. 创建监听器（TCP&a…...

编程日记 2025/5/3 18:33:38

第一章：A Primer on Memory Consistency and Cache Coherence - 2nd Edition

引言： 许多现代计算机系统，包括同构和异构架构的系统，都在硬件层面支持共享内存。在共享内存系统中，每个处理器核心都可以对单一的共享地址空间进行读写操作。对于共享内存计算机而言，内存一致性模型定义了其内存系统在…...

编程日记 2025/5/3 18:25:25

NVIDIA Omniverse在数字孪生中的算力消耗模型构建方法

引言：虚拟实验室的算力经济学在高校虚拟实验室建设中，数字孪生系统的实时物理仿真精度与算力成本之间存在显著矛盾。以H800 GPU集群为例，单个8卡节点每秒可处理2.3亿个物理粒子交互，但若未建立精准的算力消耗模型，资…...

编程日记 2025/5/3 18:23:22

C++ 动态内存管理详讲

1. 四个全局函数的定义与作用这四个函数只负责空间的开辟和释放，不会调构造和析构 (1) ::operator new cpp void* operator new(size_t size); // 全局版本功能：分配 size 字节的未初始化内存。底层实现：调用 malloc(size)。调用场…...

编程日记 2025/5/3 18:22:17

纹理对象创建

纹理对象通俗点就是贴图，像游戏的皮肤什么就是纹理。常间的结构就是激活纹理单元（0-15有16个），将纹理对象挂在纹理单元上，纹理采样器需要采哪个样品就与哪个单元挂钩就行了，加载纹理对象需要用到stb_image库…...

编程日记 2025/5/3 18:21:15

如何利用dify 生成Fine‑tune 需要的Alpaca 格式数据

如果你选择llamafactory 格式进行微调，它只是格式是Alpaca格式，dify 的agent dsl 如下，你可以导入本地的dify 或者导入cloud 版本的；测试版本是0.1.5 app:description: 上传文件，基于文件内容，使用 Silico…...

编程日记 2025/5/3 18:09:59

软件第三方测试：关键部分、意义、流程及方法全解析？

软件第三方测试是保障软件质量的关键部分，它由专业的机构来开展，这个机构不隶属于开发方和使用方，能以客观公正的视角找出软件问题。测试意义软件第三方测试意义重大，它依靠专业技术，依照严格流程，对软…...

编程日记 2025/5/3 18:00:47

贪心算法解决会议安排问题

文章目录前言一、什么是贪心算法？ 贪心算法的基本概念：贪心算法并不从整体最优上加以考虑，所做的选择只是在某种意义上的局部最优选择。二、会议安排题目 1.题目理解 2.思路剖析总结前言本文将主要介绍贪心算法需要注意的地方以…...

编程日记 2025/5/3 17:58:44

高露洁牙膏是哪个国家的品牌？高露洁牙膏哪一款最好？

高露洁是来自于美国一个比较有知名度的品牌，在1806年的时候创立。总部是在美国纽约公园大道，在1873年时，高露洁就已经开始销售罐装牙膏。在1896年时期推出可折叠管牙膏，在口腔护理产品发展的过程中拥有着不容忽视的地位。在1992…...

编程日记 2025/5/3 17:54:39

lin接口在线计算数据帧的校验位

在线校验计算链接：https://linchecksumcalculator.machsystems.cz/ 插入图片：...

编程日记 2025/5/3 17:49:32

Linux-07-Shell

一、Shell概述: Shell是一个命令行解释器，它接受应用程序/用户命令，然后调用操作系统内核二、Shell中的变量: 1.系统预定义的变量: $HOME,$PWD,$SHELL,$USER等 2.用户自定义的变量: (1).基本语法: 定义变量:变量名变量值，注意前后不能…...

编程日记 2025/5/6 21:52:46

【云盘】使用阿里云盘托管项目大文件

【云盘】使用阿里云盘托管项目大文件由于经常需要切换服务器运行项目实验，不同服务器在项目实验过程中会产生不同的数据、模型等较大文件，不能像代码那样能够使用git托管，因此考虑使用阿里云盘作为”第三方平台“托管这些大文件。一、使用…...

编程日记 2025/5/3 17:48:28

《缓存策略：移动应用网络请求的“效能密钥” 》

用户体验无疑是重中之重，而网络请求性能，恰似一座桥梁，连接着用户与应用丰富的内容和功能。当网络不佳或者请求频繁时，缓慢的响应速度常常让用户兴致索然，甚至可能导致用户流失。此时，缓存策略就如同一位幕…...

编程日记 2025/5/3 17:45:21

深入解析C++11委托构造函数：消除冗余初始化的利器

一、传统构造函数的痛点在C11之前，当多个构造函数需要执行相同的初始化逻辑时，开发者往往面临两难选择： class DataProcessor {std::string dataPath;bool verbose;int bufferSize; public:// 基础版本DataProcessor(const std::string&am…...

编程日记 2025/5/3 17:42:17

文章七《深度学习调优与超参数优化》

🚀 文章7：深度学习调优与超参数优化——你的AI模型需要一场"整容手术" 一、模型调优核心策略：像调整游戏装备一样优化模型 1. 学习率调整：掌控训练的"油门踏板" 比喻：把模型训练想象成赛车游戏&…...

编程日记 2025/5/3 17:41:13

python入门(1)变量与输入输出

一、变量使用规则变量名值例子 a13变量名规则变量名可以用大小写字母、数字、下划线。数字、下划线不可开头例子 name name1 1name name_first _first 二、输入输出输出print print(*objects,sep"",end"\n") objects:多个要输出的值 sep:每个…...

编程日记 2025/5/3 17:40:11

藏文情感分析器入门学习实践

🎯 项目目标： 输入一段藏文短句。自动分析这句话的情感倾向：积极（正面）/消极（负面）/中立。 🔍 技术原理简介情感分析是什么？ 情感分析（Sentiment Analysi…...

编程日记 2025/5/3 17:38:07

爱胜品ICSP YPS-1133DN Plus黑白激光打印机报“自动进纸盒进纸失败”处理方法之一

故障现象如下图提示： 用户的爱胜品ICSP YPS-1133DN Plus黑白激光打印机在工作过程中提示自动进纸盒进纸失败并且红色故障灯闪烁； 给出常见故障一般处理建议如下： 当您的爱胜品ICSP YPS-1133DN Plus 黑白激光打印机出现“自动进纸盒进纸失败”…...

编程日记 2025/5/3 17:31:57

数据库索引重建与优化操作在数据库性能维护与数据更新频繁场景下的应用

数据库索引重建与优化操作在数据库性能维护与数据更新频繁场景下的应用数据库索引的作用与重要性索引的定义与作用数据库索引是一种特殊的数据结构，用于加快数据库表的数据检索速度。它类似于书籍的目录，能够快速定位到需要的数据页，而不必…...

编程日记 2025/5/3 17:30:56

前端应用开发技术历程的简要概览

前端应用开发技术详解一、萌芽期（1990s - 2004） 技术特征 HTML 3.2 / HTML 4.01 是主流版本。样式用 CSS1/CSS2，但大部分样式写在 <style> 标签甚至行内。动态效果主要通过 JavaScript 控制 DOM，兼容性极差。代表事…...

编程日记 2025/5/6 21:38:53

SPOJ 11576 TRIP2 - A Famous King’s Trip 【Tarjan+欧拉回路】

自我吐槽 （哭题目传送门 SPOJ 洛谷题目大意让你在简单无向图上删去2条边，使该图联通并存在欧拉回路输出字典序最小的一对边思路考虑到存在欧拉回路的充要条件，即 i n x ≡ 0 ( m o d 2 ) ∀ i ( 1 ≤ i ≤ n ) in_x\equiv 0 (\m…...

编程日记 2025/5/3 17:28:50

DeepSeek R1：强化学习范式的推理强化模型

定位与目标 DeepSeek R1 的推出并非 DeepSeek V3 的简单迭代，而是一次在训练范式上的大胆探索。与传统大模型主要依靠监督微调(SFT)后进行强化学习不同，R1 将重点放在推理能力和行为对齐上，尝试通过大规模强化学习直接激发模型的推理潜力。其目标是利用强化学习的反馈机制，…...

编程日记 2025/5/3 17:24:41

ubuntu22.04安装显卡驱动与cuda+cuDNN

背景： 紧接前文：Proxmox VE 8.4 显卡直通完整指南：NVIDIA 2080 Ti 实战。在R740服务器完成了proxmox的安装，并且安装了一张2080ti 魔改22g显存的的显卡。配置完了proxmox显卡直通，并将显卡挂载到了vm 301（…...

编程日记 2025/5/3 17:21:34

使用python爬取百度搜索中关于python相关的数据信息

Python爬取百度搜索"Python"相关数据信息一、准备工作在开始爬取之前，需要了解以下几点： 百度搜索有反爬机制，需要合理设置请求头百度搜索结果页面结构可能会变化需要遵守robots.txt协议（百度允许爬取搜索结果&…...

编程日记 2025/5/3 17:21:32

Bootstrap（自助法）：无需假设分布的统计推断工具

核心思想 Bootstrap 是一种重采样（Resampling）技术，通过在原始数据中有放回地重复抽样，生成大量新样本集，用于估计统计量（如均值、方差）的分布或模型性能的不确定性。 …...

编程日记 2025/5/3 17:20:31

lib和dll介绍和VS2019生成实例

目录 lib文件和dll文件的作用dll和lib的优缺点VS2019 编译YOLOv5的dll和lib lib文件和dll文件的作用 (1)lib是编译时需要的，dll是运行时需要的。如果要完成源代码的编译，有lib就够了。如果也使动态连接的程序运行起来，有dll就够了。在开发…...

编程日记 2025/5/3 17:18:27

tinycudann安装过程加ubuntu18.04gcc版本的升级（成功版！！！！）

使用的是 Linux，安装以下软件包 sudo apt-get install build-essential git安装 CUDA 并将 CUDA 安装添加到您的 PATH。例如，如果您有 CUDA 12.6.3，请将以下内容添加到您的/usr/local/~/.bashrcexport PATH"/usr/local/cuda-12.6.3/bi…...

编程日记 2025/5/3 17:17:25

数字智慧方案5869丨智慧健康医疗养老大数据整体规划方案（76页PPT）（文末有下载方式）

资料解读：智慧健康医疗养老大数据整体规划方案详细资料请看本解读文章的最后内容。随着科技的飞速发展，健康医疗领域正经历着一场深刻的变革。特别是在大数据和人工智能技术的推动下，智慧健康医疗养老的整体规划方案逐渐浮出水面。本文将…...

编程日记 2025/5/3 17:16:24

使用huggingface_hub需要注意的事项

在安装huggingface_hub的时候要注意如果你的python是放在c盘下时记得用管理员模式命令行来安装huggingface_hub，否则安装过程会报错，之后也不会有huggingface-cli命令。如果安装时因为没有用管理员权限安装而报错了，可以先卸载huggingface-…...

编程日记 2025/5/3 17:02:01

Matplotlib核心课程-2

4.1 数据加载、储存 4.1.1 从数据文件读取数据导入支持库： import numpy as np from pandas import Series,DataFrame import pandas as pd 从csv文件读取数据，一般方法： pd.read_csv(../data/ex1.csv,encodinggbk) 从csv文件读取数据&#…...

编程日记 2025/5/3 17:00:58

友元函数和友元类

友元友元是 C 提供的一种打破封装的机制，允许友元函数或友元类访问某个类的非公有成员（private/protected）。友元函数友元函数可以直接访问类的所有成员，它是定义在类外部的普通函数 ，不属于任何类…...

编程日记 2025/5/3 16:56:49

5.2刷题

P1064 [NOIP 2006 提高组] 金明的预算方案背包＋附属品DP #include<bits/stdc.h> using namespace std; #define int long long int n, m, v, p, q; struct node{int id, v, s, f; }a[100]; int b[32010], dp[32010]; bool cmp(node a, node b){if(a.id b.…...

编程日记 2025/5/3 16:55:44