当前位置: 首页 > 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…...

观成科技:隐蔽隧道工具Ligolo-ng加密流量分析

1.工具介绍 Ligolo-ng是一款由go编写的高效隧道工具&#xff0c;该工具基于TUN接口实现其功能&#xff0c;利用反向TCP/TLS连接建立一条隐蔽的通信信道&#xff0c;支持使用Let’s Encrypt自动生成证书。Ligolo-ng的通信隐蔽性体现在其支持多种连接方式&#xff0c;适应复杂网…...

JavaSec-RCE

简介 RCE(Remote Code Execution)&#xff0c;可以分为:命令注入(Command Injection)、代码注入(Code Injection) 代码注入 1.漏洞场景&#xff1a;Groovy代码注入 Groovy是一种基于JVM的动态语言&#xff0c;语法简洁&#xff0c;支持闭包、动态类型和Java互操作性&#xff0c…...

Admin.Net中的消息通信SignalR解释

定义集线器接口 IOnlineUserHub public interface IOnlineUserHub {/// 在线用户列表Task OnlineUserList(OnlineUserList context);/// 强制下线Task ForceOffline(object context);/// 发布站内消息Task PublicNotice(SysNotice context);/// 接收消息Task ReceiveMessage(…...

Vue3 + Element Plus + TypeScript中el-transfer穿梭框组件使用详解及示例

使用详解 Element Plus 的 el-transfer 组件是一个强大的穿梭框组件&#xff0c;常用于在两个集合之间进行数据转移&#xff0c;如权限分配、数据选择等场景。下面我将详细介绍其用法并提供一个完整示例。 核心特性与用法 基本属性 v-model&#xff1a;绑定右侧列表的值&…...

DAY 47

三、通道注意力 3.1 通道注意力的定义 # 新增&#xff1a;通道注意力模块&#xff08;SE模块&#xff09; class ChannelAttention(nn.Module):"""通道注意力模块(Squeeze-and-Excitation)"""def __init__(self, in_channels, reduction_rat…...

Frozen-Flask :将 Flask 应用“冻结”为静态文件

Frozen-Flask 是一个用于将 Flask 应用“冻结”为静态文件的 Python 扩展。它的核心用途是&#xff1a;将一个 Flask Web 应用生成成纯静态 HTML 文件&#xff0c;从而可以部署到静态网站托管服务上&#xff0c;如 GitHub Pages、Netlify 或任何支持静态文件的网站服务器。 &am…...

论文解读:交大港大上海AI Lab开源论文 | 宇树机器人多姿态起立控制强化学习框架(一)

宇树机器人多姿态起立控制强化学习框架论文解析 论文解读&#xff1a;交大&港大&上海AI Lab开源论文 | 宇树机器人多姿态起立控制强化学习框架&#xff08;一&#xff09; 论文解读&#xff1a;交大&港大&上海AI Lab开源论文 | 宇树机器人多姿态起立控制强化…...

稳定币的深度剖析与展望

一、引言 在当今数字化浪潮席卷全球的时代&#xff0c;加密货币作为一种新兴的金融现象&#xff0c;正以前所未有的速度改变着我们对传统货币和金融体系的认知。然而&#xff0c;加密货币市场的高度波动性却成为了其广泛应用和普及的一大障碍。在这样的背景下&#xff0c;稳定…...

佰力博科技与您探讨热释电测量的几种方法

热释电的测量主要涉及热释电系数的测定&#xff0c;这是表征热释电材料性能的重要参数。热释电系数的测量方法主要包括静态法、动态法和积分电荷法。其中&#xff0c;积分电荷法最为常用&#xff0c;其原理是通过测量在电容器上积累的热释电电荷&#xff0c;从而确定热释电系数…...

浪潮交换机配置track检测实现高速公路收费网络主备切换NQA

浪潮交换机track配置 项目背景高速网络拓扑网络情况分析通信线路收费网络路由 收费汇聚交换机相应配置收费汇聚track配置 项目背景 在实施省内一条高速公路时遇到的需求&#xff0c;本次涉及的主要是收费汇聚交换机的配置&#xff0c;浪潮网络设备在高速项目很少&#xff0c;通…...