【算法】石子合并(区间dp)
题目
设有 N 堆石子排成一排,其编号为 1,2,3,…,N。
每堆石子有一定的质量,可以用一个整数来描述,现在要将这 N 堆石子合并成为一堆。
每次只能合并相邻的两堆,合并的代价为这两堆石子的质量之和,合并后与这两堆石子相邻的石子将和新堆相邻,合并时由于选择的顺序不同,合并的总代价也不相同。
例如有 4 堆石子分别为 1 3 5 2, 我们可以先合并 1、2 堆,代价为 4,得到 4 5 2, 又合并 1、2 堆,代价为 9,得到 9 2 ,再合并得到 11,总代价为 4+9+11=24;
如果第二步是先合并 2、3 堆,则代价为 7,得到 4 7,最后一次合并代价为 11,总代价为 4+7+11=22。
问题是:找出一种合理的方法,使总的代价最小,输出最小代价。
输入格式
第一行一个数 N 表示石子的堆数 N。
第二行 N 个数,表示每堆石子的质量(均不超过 1000)。
输出格式
输出一个整数,表示最小代价。
数据范围
1 ≤ N ≤ 300
思路
我们得到 n 堆石子,将石子两两合并。
最外层循环:
合并长度为len的区间(从len = 2开始)
中间循环:
求出 L 与 R的值(长度为len的集合的左右边界)
最内层循环:
求出f [ l ] [ r ] 的最小值(f [ i ][ j ]中储存 i 到 j 区间合并的最小值)
代码
#include<bits/stdc++.h>
using namespace std;
const int N = 310;
int n;
int s[N];// 前i堆石子的前缀和
int f[N][N];// 表示i到j这个区间合并的最小花费int main()
{cin >> n;for(int i = 1; i <= n; i ++) cin >> s[i];// 输入每堆石子的个数for(int i = 1; i <= n; i ++) s[i] += s[i - 1];// 求出前i堆石子的前缀和for(int len = 2; len <= n; len ++)// 合并长度为len的区间for(int i = 1; i + len - 1 <= n; i ++)// 求出所有长度为len集合合并的最小代价{int l = i,r = i + len - 1;// l,r分别为左右边界f[l][r] = 0x3f3f3f3f;// 给f[l][r]赋初始值for(int k = l; k < r; k ++)// k表示靠近l的区间的长度(求f[l][r]这个区间合并的最少花费)f[l][r] = min(f[l][r],f[l][k] + f[k + 1][r] + s[r] - s[l - 1]);}cout << f[1][n] << endl;return 0;
}
相关文章:
【算法】石子合并(区间dp)
题目 设有 N 堆石子排成一排,其编号为 1,2,3,…,N。 每堆石子有一定的质量,可以用一个整数来描述,现在要将这 N 堆石子合并成为一堆。 每次只能合并相邻的两堆,合并的代价为这两堆石子的质量之和,合并后与这两堆石子…...
C++-特殊类和单例模式
1.请设计一个类,不能被拷贝 拷贝构造函数以及赋值运算符重载,因此想要让一个类禁止拷贝,只需让该类不能调用拷贝构造函数以及赋值运算符重载即可。 //该类不能发生拷贝class NonCopy{public:NonCopy(const NonCopy& Nc) delete;NonCopy&…...
【开源】基于Vue.js的智能教学资源库系统
项目编号: S 050 ,文末获取源码。 \color{red}{项目编号:S050,文末获取源码。} 项目编号:S050,文末获取源码。 目录 一、摘要1.1 项目介绍1.2 项目录屏 二、功能模块2.1 数据中心模块2.2 课程档案模块2.3 课…...
C语言之qsort()函数的模拟实现
C语言之qsort()函数的模拟实现 文章目录 C语言之qsort()函数的模拟实现1. 简介2. 冒泡排序3. 对冒泡排序进行改造4. 改造部分4.1 保留部分的冒泡排序4.2 比较部分4.3 交换部分 5. bubble_sort2完整代码6. 使用bubble_sort2来排序整型数组7. 使用bubble_sort2来排序结构体数组7.…...
数字化未来:实时云渲染在智慧城市中的创新应用
数字中国战略"是国家推动数字经济发展的战略框架。这个战略旨在加速数字化转型,推动信息技术在各个领域的应用,提高社会经济效益和人民生活质量。而智慧城市作为其中的重要一环,重要性不言而喻。 智慧城市是当今城市发展的热点和趋势&a…...
Go语言常用命令详解(二)
文章目录 前言常用命令go bug示例参数说明 go doc示例参数说明 go env示例 go fix示例 go fmt示例 go generate示例 总结写在最后 前言 接着上一篇继续介绍Go语言的常用命令 常用命令 以下是一些常用的Go命令,这些命令可以帮助您在Go开发中进行编译、测试、运行和…...
ChatGPT 从零到一打造私人智能英语学习助手
近几年,随着智能化技术的发展和人工智能的兴起,越来越多的应用程序开始涌现出来。在这些应用中,语音识别、自然语言处理以及机器翻译等技术都得到了广泛的应用。其中,聊天机器人成为了最受欢迎的人工智能应用之一,它们…...
算法升级之路(七)-盛最多水的容器
给定一个长度为 n 的整数数组 height 。有 n 条垂线,第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。 找出其中的两条线,使得它们与 x 轴共同构成的容器可以容纳最多的水。 返回容器可以储存的最大水量。 原题链接: 盛最多水的容器 解题思路&…...
milvus数据库索引管理
一、建立向量索引 默认情况下,Milvus不会对小于1,024行的段进行索引。 1.准备索引参数 index_params {"metric_type":"L2","index_type":"IVF_FLAT","params":{"nlist":1024} } #"nlist"…...
JVM中的 -Xms参数 设置 JVM 的初始堆大小
在 Java 虚拟机(JVM)的配置中,-Xms 是一个启动参数,用于设置 JVM 的初始堆大小(Initial Heap Size)。这个参数对于优化 Java 应用程序的性能非常重要,特别是在处理需要大量内存的应用程序时。 …...
Idea 创建 Spring 项目(保姆级)
描述信息 最近卷起来,系统学习Spring;俗话说:万事开头难;创建一个Spring项目在网上找了好久没有找到好的方式;摸索了半天产出如下文档。 在 Idea 中新建项目 填写信息如下 生成项目目录结构 pom添加依赖 <depende…...
C++多线程学习(一):C++11 多线程快速入门
参考引用 C11 14 17 20 多线程从原理到线程池实战代码运行环境:Visual Studio 2019 1. 为什么要用多线程 任务分解 耗时的操作,任务分解,实时响应 数据分解 充分利用多核CPU处理数据 数据流分解 读写分离,解耦合设计 2. 第一个…...
Linux系统之lsof命令的基本使用
Linux系统之lsof命令的基本使用 一、lsof命令的基本使用二、lsof命令的使用帮助2.1 lsof命令的help帮助信息2.2 lsof命令帮助解释 三、lsof的基本使用3.1 直接使用lsof命令3.2 查看某个进程打开的所有文件3.3 查看某个用户打开的所有文件3.4 查看某个文件被哪些进程打开3.5 查看…...
性能压力测试的优势与重要性
性能压力测试是软件开发过程中至关重要的一环,它通过模拟系统在极限条件下的运行,以评估系统在正常和异常负载下的表现。这种测试为确保软件系统的可靠性、稳定性和可伸缩性提供了关键信息。下面将探讨性能压力测试的优势以及为什么在软件开发中它具有不…...
AtCoder Beginner Contest 329 题解A~F
A - Spread 输入字符串,字符之间加上空格输出 B - Next 输出数组当中第二大的数 C - Count xxx 统计每个字符出现过的最长长度,再累加即可 #include<bits/stdc.h> #pragma GCC optimize("Ofast") #define INF 0x3f3f3f3f #define I…...
Windows网络「SSL错误问题」及解决方案
文章目录 问题方案 问题 当我们使用了神秘力量加持网络后,可能会和国内的镜像源网站的之间发生冲突,典型的有 Python 从网络中安装包,如执行 pip install pingouin 时,受网络影响导致无法完成安装的情况: pip config…...
python数据可视化
绘制简单的折线图 1.1json数据格式 JSON是一种轻量级的数据交互格式。可以按照JSON指定的格式去组织和封装数据,其本质上是一个带有特定格式的字符串。 主要功能:json就是一种在各个编程语言中流通的数据格式,负责不同编程语言中的数据传递…...
LV.12 D18 中断处理 学习笔记
一、ARM的异常处理机制及工程代码结构 1.1异常概念 处理器在正常执行程序的过程中可能会遇到一些不正常的事件发生 这时处理器就要将当前的程序暂停下来转而去处理这个异常的事件 异常事件处理完成之后再返回到被异常打断的点继续执行程序。 1.2异常处理机制 不同的处…...
蓝桥杯每日一题2023.11.19
题目描述 “蓝桥杯”练习系统 (lanqiao.cn) 题目分析 首先想到的方法为dfs去寻找每一个数,但发现会有超时 #include<bits/stdc.h> using namespace std; const int N 2e5 10; int n, cnt, a[N]; void dfs(int dep, int sum, int start) {if(dep 4){if(s…...
<b><strong>,<i><em>标签的区别
1. b标签和strong标签 b标签:仅仅是UI层面的加粗样式,并不具备HTML语义 strong标签:不仅是在UI层面的加粗样式,具备HTML语义,表示强调 2. i标签和em标签 i 标签:仅仅是UI层面的斜体样式,并不具备…...
在软件开发中正确使用MySQL日期时间类型的深度解析
在日常软件开发场景中,时间信息的存储是底层且核心的需求。从金融交易的精确记账时间、用户操作的行为日志,到供应链系统的物流节点时间戳,时间数据的准确性直接决定业务逻辑的可靠性。MySQL作为主流关系型数据库,其日期时间类型的…...
springboot 百货中心供应链管理系统小程序
一、前言 随着我国经济迅速发展,人们对手机的需求越来越大,各种手机软件也都在被广泛应用,但是对于手机进行数据信息管理,对于手机的各种软件也是备受用户的喜爱,百货中心供应链管理系统被用户普遍使用,为方…...
Debian系统简介
目录 Debian系统介绍 Debian版本介绍 Debian软件源介绍 软件包管理工具dpkg dpkg核心指令详解 安装软件包 卸载软件包 查询软件包状态 验证软件包完整性 手动处理依赖关系 dpkg vs apt Debian系统介绍 Debian 和 Ubuntu 都是基于 Debian内核 的 Linux 发行版ÿ…...
Cesium1.95中高性能加载1500个点
一、基本方式: 图标使用.png比.svg性能要好 <template><div id"cesiumContainer"></div><div class"toolbar"><button id"resetButton">重新生成点</button><span id"countDisplay&qu…...
质量体系的重要
质量体系是为确保产品、服务或过程质量满足规定要求,由相互关联的要素构成的有机整体。其核心内容可归纳为以下五个方面: 🏛️ 一、组织架构与职责 质量体系明确组织内各部门、岗位的职责与权限,形成层级清晰的管理网络…...
LLM基础1_语言模型如何处理文本
基于GitHub项目:https://github.com/datawhalechina/llms-from-scratch-cn 工具介绍 tiktoken:OpenAI开发的专业"分词器" torch:Facebook开发的强力计算引擎,相当于超级计算器 理解词嵌入:给词语画"…...
CMake 从 GitHub 下载第三方库并使用
有时我们希望直接使用 GitHub 上的开源库,而不想手动下载、编译和安装。 可以利用 CMake 提供的 FetchContent 模块来实现自动下载、构建和链接第三方库。 FetchContent 命令官方文档✅ 示例代码 我们将以 fmt 这个流行的格式化库为例,演示如何: 使用 FetchContent 从 GitH…...
Android 之 kotlin 语言学习笔记三(Kotlin-Java 互操作)
参考官方文档:https://developer.android.google.cn/kotlin/interop?hlzh-cn 一、Java(供 Kotlin 使用) 1、不得使用硬关键字 不要使用 Kotlin 的任何硬关键字作为方法的名称 或字段。允许使用 Kotlin 的软关键字、修饰符关键字和特殊标识…...
.Net Framework 4/C# 关键字(非常用,持续更新...)
一、is 关键字 is 关键字用于检查对象是否于给定类型兼容,如果兼容将返回 true,如果不兼容则返回 false,在进行类型转换前,可以先使用 is 关键字判断对象是否与指定类型兼容,如果兼容才进行转换,这样的转换是安全的。 例如有:首先创建一个字符串对象,然后将字符串对象隐…...
MySQL账号权限管理指南:安全创建账户与精细授权技巧
在MySQL数据库管理中,合理创建用户账号并分配精确权限是保障数据安全的核心环节。直接使用root账号进行所有操作不仅危险且难以审计操作行为。今天我们来全面解析MySQL账号创建与权限分配的专业方法。 一、为何需要创建独立账号? 最小权限原则…...
