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

【算法】石子合并(区间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 堆石子排成一排&#xff0c;其编号为 1,2,3,…,N。 每堆石子有一定的质量&#xff0c;可以用一个整数来描述&#xff0c;现在要将这 N 堆石子合并成为一堆。 每次只能合并相邻的两堆&#xff0c;合并的代价为这两堆石子的质量之和&#xff0c;合并后与这两堆石子…...

C++-特殊类和单例模式

1.请设计一个类&#xff0c;不能被拷贝 拷贝构造函数以及赋值运算符重载&#xff0c;因此想要让一个类禁止拷贝&#xff0c;只需让该类不能调用拷贝构造函数以及赋值运算符重载即可。 //该类不能发生拷贝class NonCopy{public:NonCopy(const NonCopy& Nc) delete;NonCopy&…...

【开源】基于Vue.js的智能教学资源库系统

项目编号&#xff1a; S 050 &#xff0c;文末获取源码。 \color{red}{项目编号&#xff1a;S050&#xff0c;文末获取源码。} 项目编号&#xff1a;S050&#xff0c;文末获取源码。 目录 一、摘要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.…...

数字化未来:实时云渲染在智慧城市中的创新应用

数字中国战略"是国家推动数字经济发展的战略框架。这个战略旨在加速数字化转型&#xff0c;推动信息技术在各个领域的应用&#xff0c;提高社会经济效益和人民生活质量。而智慧城市作为其中的重要一环&#xff0c;重要性不言而喻。 智慧城市是当今城市发展的热点和趋势&a…...

Go语言常用命令详解(二)

文章目录 前言常用命令go bug示例参数说明 go doc示例参数说明 go env示例 go fix示例 go fmt示例 go generate示例 总结写在最后 前言 接着上一篇继续介绍Go语言的常用命令 常用命令 以下是一些常用的Go命令&#xff0c;这些命令可以帮助您在Go开发中进行编译、测试、运行和…...

ChatGPT 从零到一打造私人智能英语学习助手

近几年&#xff0c;随着智能化技术的发展和人工智能的兴起&#xff0c;越来越多的应用程序开始涌现出来。在这些应用中&#xff0c;语音识别、自然语言处理以及机器翻译等技术都得到了广泛的应用。其中&#xff0c;聊天机器人成为了最受欢迎的人工智能应用之一&#xff0c;它们…...

算法升级之路(七)-盛最多水的容器

给定一个长度为 n 的整数数组 height 。有 n 条垂线&#xff0c;第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。 找出其中的两条线&#xff0c;使得它们与 x 轴共同构成的容器可以容纳最多的水。 返回容器可以储存的最大水量。 原题链接: 盛最多水的容器 解题思路&…...

milvus数据库索引管理

一、建立向量索引 默认情况下&#xff0c;Milvus不会对小于1,024行的段进行索引。 1.准备索引参数 index_params {"metric_type":"L2","index_type":"IVF_FLAT","params":{"nlist":1024} } #"nlist"…...

JVM中的 -Xms参数 设置 JVM 的初始堆大小

在 Java 虚拟机&#xff08;JVM&#xff09;的配置中&#xff0c;-Xms 是一个启动参数&#xff0c;用于设置 JVM 的初始堆大小&#xff08;Initial Heap Size&#xff09;。这个参数对于优化 Java 应用程序的性能非常重要&#xff0c;特别是在处理需要大量内存的应用程序时。 …...

Idea 创建 Spring 项目(保姆级)

描述信息 最近卷起来&#xff0c;系统学习Spring&#xff1b;俗话说&#xff1a;万事开头难&#xff1b;创建一个Spring项目在网上找了好久没有找到好的方式&#xff1b;摸索了半天产出如下文档。 在 Idea 中新建项目 填写信息如下 生成项目目录结构 pom添加依赖 <depende…...

C++多线程学习(一):C++11 多线程快速入门

参考引用 C11 14 17 20 多线程从原理到线程池实战代码运行环境&#xff1a;Visual Studio 2019 1. 为什么要用多线程 任务分解 耗时的操作&#xff0c;任务分解&#xff0c;实时响应 数据分解 充分利用多核CPU处理数据 数据流分解 读写分离&#xff0c;解耦合设计 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 查看…...

性能压力测试的优势与重要性

性能压力测试是软件开发过程中至关重要的一环&#xff0c;它通过模拟系统在极限条件下的运行&#xff0c;以评估系统在正常和异常负载下的表现。这种测试为确保软件系统的可靠性、稳定性和可伸缩性提供了关键信息。下面将探讨性能压力测试的优势以及为什么在软件开发中它具有不…...

AtCoder Beginner Contest 329 题解A~F

A - Spread 输入字符串&#xff0c;字符之间加上空格输出 B - Next 输出数组当中第二大的数 C - Count xxx 统计每个字符出现过的最长长度&#xff0c;再累加即可 #include<bits/stdc.h> #pragma GCC optimize("Ofast") #define INF 0x3f3f3f3f #define I…...

Windows网络「SSL错误问题」及解决方案

文章目录 问题方案 问题 当我们使用了神秘力量加持网络后&#xff0c;可能会和国内的镜像源网站的之间发生冲突&#xff0c;典型的有 Python 从网络中安装包&#xff0c;如执行 pip install pingouin 时&#xff0c;受网络影响导致无法完成安装的情况&#xff1a; pip config…...

python数据可视化

绘制简单的折线图 1.1json数据格式 JSON是一种轻量级的数据交互格式。可以按照JSON指定的格式去组织和封装数据&#xff0c;其本质上是一个带有特定格式的字符串。 主要功能&#xff1a;json就是一种在各个编程语言中流通的数据格式&#xff0c;负责不同编程语言中的数据传递…...

LV.12 D18 中断处理 学习笔记

一、ARM的异常处理机制及工程代码结构 1.1异常概念 处理器在正常执行程序的过程中可能会遇到一些不正常的事件发生 这时处理器就要将当前的程序暂停下来转而去处理这个异常的事件 异常事件处理完成之后再返回到被异常打断的点继续执行程序。 1.2异常处理机制 不同的处…...

蓝桥杯每日一题2023.11.19

题目描述 “蓝桥杯”练习系统 (lanqiao.cn) 题目分析 首先想到的方法为dfs去寻找每一个数&#xff0c;但发现会有超时 #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标签&#xff1a;仅仅是UI层面的加粗样式&#xff0c;并不具备HTML语义 strong标签&#xff1a;不仅是在UI层面的加粗样式&#xff0c;具备HTML语义&#xff0c;表示强调 2. i标签和em标签 i 标签&#xff1a;仅仅是UI层面的斜体样式&#xff0c;并不具备…...

龙虎榜——20250610

上证指数放量收阴线&#xff0c;个股多数下跌&#xff0c;盘中受消息影响大幅波动。 深证指数放量收阴线形成顶分型&#xff0c;指数短线有调整的需求&#xff0c;大概需要一两天。 2025年6月10日龙虎榜行业方向分析 1. 金融科技 代表标的&#xff1a;御银股份、雄帝科技 驱动…...

DockerHub与私有镜像仓库在容器化中的应用与管理

哈喽&#xff0c;大家好&#xff0c;我是左手python&#xff01; Docker Hub的应用与管理 Docker Hub的基本概念与使用方法 Docker Hub是Docker官方提供的一个公共镜像仓库&#xff0c;用户可以在其中找到各种操作系统、软件和应用的镜像。开发者可以通过Docker Hub轻松获取所…...

线程与协程

1. 线程与协程 1.1. “函数调用级别”的切换、上下文切换 1. 函数调用级别的切换 “函数调用级别的切换”是指&#xff1a;像函数调用/返回一样轻量地完成任务切换。 举例说明&#xff1a; 当你在程序中写一个函数调用&#xff1a; funcA() 然后 funcA 执行完后返回&…...

Vue2 第一节_Vue2上手_插值表达式{{}}_访问数据和修改数据_Vue开发者工具

文章目录 1.Vue2上手-如何创建一个Vue实例,进行初始化渲染2. 插值表达式{{}}3. 访问数据和修改数据4. vue响应式5. Vue开发者工具--方便调试 1.Vue2上手-如何创建一个Vue实例,进行初始化渲染 准备容器引包创建Vue实例 new Vue()指定配置项 ->渲染数据 准备一个容器,例如: …...

C++八股 —— 单例模式

文章目录 1. 基本概念2. 设计要点3. 实现方式4. 详解懒汉模式 1. 基本概念 线程安全&#xff08;Thread Safety&#xff09; 线程安全是指在多线程环境下&#xff0c;某个函数、类或代码片段能够被多个线程同时调用时&#xff0c;仍能保证数据的一致性和逻辑的正确性&#xf…...

【开发技术】.Net使用FFmpeg视频特定帧上绘制内容

目录 一、目的 二、解决方案 2.1 什么是FFmpeg 2.2 FFmpeg主要功能 2.3 使用Xabe.FFmpeg调用FFmpeg功能 2.4 使用 FFmpeg 的 drawbox 滤镜来绘制 ROI 三、总结 一、目的 当前市场上有很多目标检测智能识别的相关算法&#xff0c;当前调用一个医疗行业的AI识别算法后返回…...

Device Mapper 机制

Device Mapper 机制详解 Device Mapper&#xff08;简称 DM&#xff09;是 Linux 内核中的一套通用块设备映射框架&#xff0c;为 LVM、加密磁盘、RAID 等提供底层支持。本文将详细介绍 Device Mapper 的原理、实现、内核配置、常用工具、操作测试流程&#xff0c;并配以详细的…...

#Uniapp篇:chrome调试unapp适配

chrome调试设备----使用Android模拟机开发调试移动端页面 Chrome://inspect/#devices MuMu模拟器Edge浏览器&#xff1a;Android原生APP嵌入的H5页面元素定位 chrome://inspect/#devices uniapp单位适配 根路径下 postcss.config.js 需要装这些插件 “postcss”: “^8.5.…...

【JVM】Java虚拟机(二)——垃圾回收

目录 一、如何判断对象可以回收 &#xff08;一&#xff09;引用计数法 &#xff08;二&#xff09;可达性分析算法 二、垃圾回收算法 &#xff08;一&#xff09;标记清除 &#xff08;二&#xff09;标记整理 &#xff08;三&#xff09;复制 &#xff08;四&#xff…...

「全栈技术解析」推客小程序系统开发:从架构设计到裂变增长的完整解决方案

在移动互联网营销竞争白热化的当下&#xff0c;推客小程序系统凭借其裂变传播、精准营销等特性&#xff0c;成为企业抢占市场的利器。本文将深度解析推客小程序系统开发的核心技术与实现路径&#xff0c;助力开发者打造具有市场竞争力的营销工具。​ 一、系统核心功能架构&…...