【算法】石子合并(区间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作为主流关系型数据库,其日期时间类型的…...
vscode里如何用git
打开vs终端执行如下: 1 初始化 Git 仓库(如果尚未初始化) git init 2 添加文件到 Git 仓库 git add . 3 使用 git commit 命令来提交你的更改。确保在提交时加上一个有用的消息。 git commit -m "备注信息" 4 …...
设计模式和设计原则回顾
设计模式和设计原则回顾 23种设计模式是设计原则的完美体现,设计原则设计原则是设计模式的理论基石, 设计模式 在经典的设计模式分类中(如《设计模式:可复用面向对象软件的基础》一书中),总共有23种设计模式,分为三大类: 一、创建型模式(5种) 1. 单例模式(Sing…...
<6>-MySQL表的增删查改
目录 一,create(创建表) 二,retrieve(查询表) 1,select列 2,where条件 三,update(更新表) 四,delete(删除表…...
进程地址空间(比特课总结)
一、进程地址空间 1. 环境变量 1 )⽤户级环境变量与系统级环境变量 全局属性:环境变量具有全局属性,会被⼦进程继承。例如当bash启动⼦进程时,环 境变量会⾃动传递给⼦进程。 本地变量限制:本地变量只在当前进程(ba…...
QMC5883L的驱动
简介 本篇文章的代码已经上传到了github上面,开源代码 作为一个电子罗盘模块,我们可以通过I2C从中获取偏航角yaw,相对于六轴陀螺仪的yaw,qmc5883l几乎不会零飘并且成本较低。 参考资料 QMC5883L磁场传感器驱动 QMC5883L磁力计…...
Linux相关概念和易错知识点(42)(TCP的连接管理、可靠性、面临复杂网络的处理)
目录 1.TCP的连接管理机制(1)三次握手①握手过程②对握手过程的理解 (2)四次挥手(3)握手和挥手的触发(4)状态切换①挥手过程中状态的切换②握手过程中状态的切换 2.TCP的可靠性&…...
AspectJ 在 Android 中的完整使用指南
一、环境配置(Gradle 7.0 适配) 1. 项目级 build.gradle // 注意:沪江插件已停更,推荐官方兼容方案 buildscript {dependencies {classpath org.aspectj:aspectjtools:1.9.9.1 // AspectJ 工具} } 2. 模块级 build.gradle plu…...
Aspose.PDF 限制绕过方案:Java 字节码技术实战分享(仅供学习)
Aspose.PDF 限制绕过方案:Java 字节码技术实战分享(仅供学习) 一、Aspose.PDF 简介二、说明(⚠️仅供学习与研究使用)三、技术流程总览四、准备工作1. 下载 Jar 包2. Maven 项目依赖配置 五、字节码修改实现代码&#…...
【Linux】Linux 系统默认的目录及作用说明
博主介绍:✌全网粉丝23W,CSDN博客专家、Java领域优质创作者,掘金/华为云/阿里云/InfoQ等平台优质作者、专注于Java技术领域✌ 技术范围:SpringBoot、SpringCloud、Vue、SSM、HTML、Nodejs、Python、MySQL、PostgreSQL、大数据、物…...
