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

区间dp,合并石子模板题

设有 N 堆石子排成一排,其编号为 1,2,3,…,N。

每堆石子有一定的质量,可以用一个整数来描述,现在要将这 N 堆石子合并成为一堆。

每次只能合并相邻的两堆,合并的代价为这两堆石子的质量之和,合并后与这两堆石子相邻的石子将和新堆相邻,合并时由于选择的顺序不同,合并的总代价也不相同。

例如有 44 堆石子分别为 1 3 5 2, 我们可以先合并 1、2堆,代价为 44,得到 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

输入样例:

4
1 3 5 2

输出样例:

22
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<string>
#include<cstring>
#include<cmath>
#include<ctime>
#include<algorithm>
#include<utility>
#include<stack>
#include<queue>
#include<vector>
#include<set>
#include<map>
using namespace std;
typedef long long LL;
const int N = 300 + 5;
const int INF = 1e9;
int n;
int sum[N], dp[N][N];int main() {cin >> n;for (int i = 1; i <= n; i++) {scanf("%d", &sum[i]);sum[i] += sum[i - 1];}for (int len = 2; len <= n; len++) {for (int l = 1; l + len - 1 <= n; l++) {int r = len + l - 1;dp[l][r] = INF;for (int k = l; k < r; k++) {dp[l][r] = min(dp[l][r], dp[l][k] + dp[k + 1][r] + sum[r] - sum[l - 1]);}}}cout << dp[1][n] << endl;return 0;
}

代码2

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<string>
#include<cstring>
#include<cmath>
#include<ctime>
#include<algorithm>
#include<utility>
#include<stack>
#include<queue>
#include<vector>
#include<set>
#include<map>
using namespace std;
typedef long long LL;
const int N = 300 + 5;
const int INF = 1e9;
int n;
LL sum[N], dp[N][N];int main() {cin >> n;for (int i = 1; i <= n; i++) {scanf("%ld", &sum[i]);sum[i] += sum[i - 1];}for (int i = n; i >= 1; i--) {for (int j = i + 1; j <= n; j++) {dp[i][j] = INF;for (int k = i; k < j; k++) {dp[i][j] = min(dp[i][j], dp[i][k] + dp[k + 1][j] + sum[j] - sum[i - 1]);}}}cout << dp[1][n] << endl;return 0;
}

 

相关文章:

区间dp,合并石子模板题

设有 N 堆石子排成一排&#xff0c;其编号为 1,2,3,…,N。 每堆石子有一定的质量&#xff0c;可以用一个整数来描述&#xff0c;现在要将这 N 堆石子合并成为一堆。 每次只能合并相邻的两堆&#xff0c;合并的代价为这两堆石子的质量之和&#xff0c;合并后与这两堆石子相邻的…...

C++代码格式化工具clang-format详细介绍

文章目录 clang-format思考代码风格指南生成您的配置运行 clang-format禁用一段代码的格式设置clang-format的设置预览 clang-format 我曾在许多编程团队工作过&#xff0c;这些团队名义上都有“编程风格指南”。该指南经常被写下来并放置在开发人员很少查看的地方。几乎在每种…...

CentOS 7安装PostgreSQL 15版本数据库

目录 一、何为PostgreSQL&#xff1f; 二、PostgreSQL安装 2.1安装依赖 2.2 执行安装 2.3 数据库初始化 2.4 配置环境变量 2.5 创建数据库 2.6 配置远程 2.7 测试远程 三、常用命令 四、用户创建和数据库权限 一、何为PostgreSQL&#xff1f; PostgreSQL是以加州大学…...

QGraphicsView实现简易地图2『瓦片经纬度』

前文链接&#xff1a;QGraphicsView实现简易地图1『加载离线瓦片地图』 地图采用GCJ02 Web 墨卡托投影&#xff0c;最小坐标&#xff1a;(-180.00000000000000,-85.05112877980655)&#xff0c;最大坐标&#xff1a;(180.00000000000000,85.05112877980655)。瓦片地图单张图片像…...

医学图像重建—第一章笔记

序言 本书涵盖内容&#xff1a; 2D parallel beam imaging 2D fan beam imaging 3D parallel ray imaging 3D parallel plane imaging 3D cone beam imaging 算法包括&#xff1a;analytical method&#xff0c;iterative method 应用于&#xff1a; X-ray CT single photon…...

python-pytorch基础之神经网络分类

这里写目录标题 生成数据函数定义数据集定义loader加载数据定义神经网络模型测试输出是否为2个输入数据&#xff0c;输出结果 训练模型函数计算正确率 训练数据并保存模型测试模型准备数据加载模型预测对比结果 生成数据函数 import randomdef get_rectangle():widthrandom.ra…...

【C++ 程序设计】实战:C++ 变量实践练习题

目录 01. 变量&#xff1a;定义 02. 变量&#xff1a;初始化 03. 变量&#xff1a;参数传递 04. 变量&#xff1a;格式说明符 ① 占位符 “%d” 改为格式说明符 “%llu” ② 占位符 “%d” 改为格式说明符 “%f” 或 “%e” 05. 变量&#xff1a;字节数统计 06. 变量&a…...

微软对Visual Studio 17.7 Preview 4进行版本更新,新插件管理器亮相

近期微软发布了Visual Studio 17.7 Preview 4版本&#xff0c;而在这个版本当中&#xff0c;全新设计的扩展插件管理器将亮相&#xff0c;并且可以让用户可更简单地安装和管理扩展插件。 据了解&#xff0c;目前用户可以从 Visual Studio Marketplace 下载各式各样的 VS 扩展插…...

Kafka 入门到起飞 - Kafka怎么做到保障消息不会重复消费的? 消费者组是什么?

Kafka怎么做到避免消息重复消费的&#xff1f; 消费者组是什么&#xff1f; 消费者&#xff1a; 1、订阅Topic&#xff08;主题&#xff09; 2、从订阅的Topic消费&#xff08;pull&#xff09;消息&#xff0c; 3、将消费消息的offset&#xff08;偏移量&#xff09;保存在K…...

MongoDB 的增、查、改、删

Monogo使用 增 单条增加 db.member.insertOne({"name":"张三","age":18,"create":new Date()}) db.member.insert({"name":"李四1","age":18,"create":new Date()}) db.member.insertOne(…...

mysql常用操作命令

mysql常用操作命令 mysql:单进程多线程模型,一个SQL语句无法利用多个cpu core 一:基本命令 0.查看当前连接数 show global status like Thread$; show variables like "%timeout%"; show variables like "log_%";1.查看当前连接状态 show processlist…...

数学建模常见模型汇总

优化问题 线性规划、半定规划、几何规划、非线性规划、整数规划、多目标规划(分层序列法)、动态规划、存贮论、代理模型、响应面分析法、列生成算法 预测模型 微分方程、小波分析、回归分析、灰色预测、马尔可夫预测、时间序列分析(AR MAMA.RMA ARTMA LSTM神经网络)、混沌模…...

C#使用LINQ查询操作符实例代码(二)

目录 六、连表操作符 1、内连接2、左外连接(DefaultIfEmpty)3、组连接七、集合操作 八、分区操作符 1、Take()&#xff1a;2、TakeWhile()&#xff1a;3、Skip()&#xff1a;4、SkipWhile()&#xff1a;九、聚合操作符 1、Count&#xff1a; 返回集合项数。 2、LongCount&…...

jenkinsfile小试牛刀

序 本文主要演示一下如何用jenkinsfile来编译java服务 安装jenkins 这里使用docker来安装jenkins docker run --name jenkins-docker \ --volume $HOME/jenkins_home:/var/jenkins_home \ -p 8080:8080 jenkins/jenkins:2.416之后访问http://${yourip}:8080&#xff0c;然后…...

C++ xmake构建

文章目录 一、xmake.lua二、xmake常用语句 一、xmake.lua --xmake.luaset_project("XXX")add_rules("mode.debug", "mode.release") set_config("arch", "x64")if is_plat("windows") then -- the release modei…...

推荐带500创作模型的付费创作V2.1.0独立版系统源码

ChatGPT 付费创作系统 V2.1.0 提供最新的对应版本小程序端&#xff0c;上一版本增加了 PC 端绘画功能&#xff0c; 绘画功能采用其他绘画接口 – 意间 AI&#xff0c;本版新增了百度文心一言接口。 后台一些小细节的优化及一些小 BUG 的处理&#xff0c;前端进行了些小细节优…...

wps图表怎么改横纵坐标,MLP 多层感知器和CNN卷积神经网络区别

目录 wps表格横纵坐标轴怎么设置&#xff1f; MLP (Multilayer Perceptron) 多层感知器 CNN (Convolutional Neural Network) 卷积神经网络 多层感知器MLP&#xff0c;全连接网络&#xff0c;DNN三者的关系 wps表格横纵坐标轴怎么设置&#xff1f; 1、打开表格点击图的右侧…...

rdb和aof

RDB持久化&#xff1a;原理是将Redis在内存中的数据库记录定时dump到磁盘上的RDB持久化AOF持久化&#xff1a;原理是将Redis的操作日志以追加的方式写入文件 rdb&#xff1a; 开启方式&#xff1a;客户端可以通过向Redis服务器发送save或bgsave命令让服务器生成rdb文件&#…...

TCP网络通信编程之网络上传文件

【图片】 【思路解析】 【客户端代码】 import java.io.*; import java.net.InetAddress; import java.net.Socket; import java.net.UnknownHostException;/*** ProjectName: Study* FileName: TCPFileUploadClient* author:HWJ* Data: 2023/7/29 18:44*/ public class TCPFil…...

Java中对Redis的常用操作

目录 数据类型五种常用数据类型介绍各种数据类型特点 常用命令字符串操作命令哈希操作命令列表操作命令集合操作命令有序集合操作命令通用命令 在Java中操作RedisRedis的Java客户端Spring Data Redis使用方式介绍环境搭建配置Redis数据源编写配置类&#xff0c;创建RedisTempla…...

PHP和Node.js哪个更爽?

先说结论&#xff0c;rust完胜。 php&#xff1a;laravel&#xff0c;swoole&#xff0c;webman&#xff0c;最开始在苏宁的时候写了几年php&#xff0c;当时觉得php真的是世界上最好的语言&#xff0c;因为当初活在舒适圈里&#xff0c;不愿意跳出来&#xff0c;就好比当初活在…...

django filter 统计数量 按属性去重

在Django中&#xff0c;如果你想要根据某个属性对查询集进行去重并统计数量&#xff0c;你可以使用values()方法配合annotate()方法来实现。这里有两种常见的方法来完成这个需求&#xff1a; 方法1&#xff1a;使用annotate()和Count 假设你有一个模型Item&#xff0c;并且你想…...

Cinnamon修改面板小工具图标

Cinnamon开始菜单-CSDN博客 设置模块都是做好的&#xff0c;比GNOME简单得多&#xff01; 在 applet.js 里增加 const Settings imports.ui.settings;this.settings new Settings.AppletSettings(this, HTYMenusonichy, instance_id); this.settings.bind(menu-icon, menu…...

Mac软件卸载指南,简单易懂!

刚和Adobe分手&#xff0c;它却总在Library里给你写"回忆录"&#xff1f;卸载的Final Cut Pro像电子幽灵般阴魂不散&#xff1f;总是会有残留文件&#xff0c;别慌&#xff01;这份Mac软件卸载指南&#xff0c;将用最硬核的方式教你"数字分手术"&#xff0…...

ElasticSearch搜索引擎之倒排索引及其底层算法

文章目录 一、搜索引擎1、什么是搜索引擎?2、搜索引擎的分类3、常用的搜索引擎4、搜索引擎的特点二、倒排索引1、简介2、为什么倒排索引不用B+树1.创建时间长,文件大。2.其次,树深,IO次数可怕。3.索引可能会失效。4.精准度差。三. 倒排索引四、算法1、Term Index的算法2、 …...

【HTTP三个基础问题】

面试官您好&#xff01;HTTP是超文本传输协议&#xff0c;是互联网上客户端和服务器之间传输超文本数据&#xff08;比如文字、图片、音频、视频等&#xff09;的核心协议&#xff0c;当前互联网应用最广泛的版本是HTTP1.1&#xff0c;它基于经典的C/S模型&#xff0c;也就是客…...

OpenLayers 分屏对比(地图联动)

注&#xff1a;当前使用的是 ol 5.3.0 版本&#xff0c;天地图使用的key请到天地图官网申请&#xff0c;并替换为自己的key 地图分屏对比在WebGIS开发中是很常见的功能&#xff0c;和卷帘图层不一样的是&#xff0c;分屏对比是在各个地图中添加相同或者不同的图层进行对比查看。…...

LLMs 系列实操科普(1)

写在前面&#xff1a; 本期内容我们继续 Andrej Karpathy 的《How I use LLMs》讲座内容&#xff0c;原视频时长 ~130 分钟&#xff0c;以实操演示主流的一些 LLMs 的使用&#xff0c;由于涉及到实操&#xff0c;实际上并不适合以文字整理&#xff0c;但还是决定尽量整理一份笔…...

libfmt: 现代C++的格式化工具库介绍与酷炫功能

libfmt: 现代C的格式化工具库介绍与酷炫功能 libfmt 是一个开源的C格式化库&#xff0c;提供了高效、安全的文本格式化功能&#xff0c;是C20中引入的std::format的基础实现。它比传统的printf和iostream更安全、更灵活、性能更好。 基本介绍 主要特点 类型安全&#xff1a…...

xmind转换为markdown

文章目录 解锁思维导图新姿势&#xff1a;将XMind转为结构化Markdown 一、认识Xmind结构二、核心转换流程详解1.解压XMind文件&#xff08;ZIP处理&#xff09;2.解析JSON数据结构3&#xff1a;递归转换树形结构4&#xff1a;Markdown层级生成逻辑 三、完整代码 解锁思维导图新…...