当前位置: 首页 > 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;并不具备…...

地震勘探——干扰波识别、井中地震时距曲线特点

目录 干扰波识别反射波地震勘探的干扰波 井中地震时距曲线特点 干扰波识别 有效波&#xff1a;可以用来解决所提出的地质任务的波&#xff1b;干扰波&#xff1a;所有妨碍辨认、追踪有效波的其他波。 地震勘探中&#xff0c;有效波和干扰波是相对的。例如&#xff0c;在反射波…...

服务器硬防的应用场景都有哪些?

服务器硬防是指一种通过硬件设备层面的安全措施来防御服务器系统受到网络攻击的方式&#xff0c;避免服务器受到各种恶意攻击和网络威胁&#xff0c;那么&#xff0c;服务器硬防通常都会应用在哪些场景当中呢&#xff1f; 硬防服务器中一般会配备入侵检测系统和预防系统&#x…...

Unit 1 深度强化学习简介

Deep RL Course ——Unit 1 Introduction 从理论和实践层面深入学习深度强化学习。学会使用知名的深度强化学习库&#xff0c;例如 Stable Baselines3、RL Baselines3 Zoo、Sample Factory 和 CleanRL。在独特的环境中训练智能体&#xff0c;比如 SnowballFight、Huggy the Do…...

3403. 从盒子中找出字典序最大的字符串 I

3403. 从盒子中找出字典序最大的字符串 I 题目链接&#xff1a;3403. 从盒子中找出字典序最大的字符串 I 代码如下&#xff1a; class Solution { public:string answerString(string word, int numFriends) {if (numFriends 1) {return word;}string res;for (int i 0;i &…...

ip子接口配置及删除

配置永久生效的子接口&#xff0c;2个IP 都可以登录你这一台服务器。重启不失效。 永久的 [应用] vi /etc/sysconfig/network-scripts/ifcfg-eth0修改文件内内容 TYPE"Ethernet" BOOTPROTO"none" NAME"eth0" DEVICE"eth0" ONBOOT&q…...

html css js网页制作成品——HTML+CSS榴莲商城网页设计(4页)附源码

目录 一、&#x1f468;‍&#x1f393;网站题目 二、✍️网站描述 三、&#x1f4da;网站介绍 四、&#x1f310;网站效果 五、&#x1fa93; 代码实现 &#x1f9f1;HTML 六、&#x1f947; 如何让学习不再盲目 七、&#x1f381;更多干货 一、&#x1f468;‍&#x1f…...

Linux离线(zip方式)安装docker

目录 基础信息操作系统信息docker信息 安装实例安装步骤示例 遇到的问题问题1&#xff1a;修改默认工作路径启动失败问题2 找不到对应组 基础信息 操作系统信息 OS版本&#xff1a;CentOS 7 64位 内核版本&#xff1a;3.10.0 相关命令&#xff1a; uname -rcat /etc/os-rele…...

CVE-2020-17519源码分析与漏洞复现(Flink 任意文件读取)

漏洞概览 漏洞名称&#xff1a;Apache Flink REST API 任意文件读取漏洞CVE编号&#xff1a;CVE-2020-17519CVSS评分&#xff1a;7.5影响版本&#xff1a;Apache Flink 1.11.0、1.11.1、1.11.2修复版本&#xff1a;≥ 1.11.3 或 ≥ 1.12.0漏洞类型&#xff1a;路径遍历&#x…...

站群服务器的应用场景都有哪些?

站群服务器主要是为了多个网站的托管和管理所设计的&#xff0c;可以通过集中管理和高效资源的分配&#xff0c;来支持多个独立的网站同时运行&#xff0c;让每一个网站都可以分配到独立的IP地址&#xff0c;避免出现IP关联的风险&#xff0c;用户还可以通过控制面板进行管理功…...

从“安全密码”到测试体系:Gitee Test 赋能关键领域软件质量保障

关键领域软件测试的"安全密码"&#xff1a;Gitee Test如何破解行业痛点 在数字化浪潮席卷全球的今天&#xff0c;软件系统已成为国家关键领域的"神经中枢"。从国防军工到能源电力&#xff0c;从金融交易到交通管控&#xff0c;这些关乎国计民生的关键领域…...