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

[区间dp]添加括号

题目描述

有一个 n n n 个元素的数组 a a a。不改变序列中每个元素在序列中的位置,把它们相加,并用括号记每次加法所得的和,称为中间和。现在要添上 n − 1 n - 1 n1 对括号,加法运算依括号顺序进行,得到 n − 1 n - 1 n1 个中间和,求出使中间和之和最小的添括号方法。


例如:给出序列是 4 , 1 , 2 , 3 4,1,2,3 4,1,2,3

第一种添括号方法:
( ( 4 + 1 ) + ( 2 + 3 ) ) = ( ( 5 ) + ( 5 ) ) = ( 10 ) ((4 + 1) + (2 +3)) = ((5) + (5)) = (10) ((4+1)+(2+3))=((5)+(5))=(10)
有三个中间和是 5 , 5 , 10 5,5,10 5,5,10 ,它们之和为: 5 + 5 + 10 = 20 5 + 5 + 10 = 20 5+5+10=20

第二种添括号方法:
( 4 + ( ( 1 + 2 ) + 3 ) ) = ( 4 + ( ( 3 ) + 3 ) ) = ( 4 + ( 6 ) ) = ( 10 ) (4 + ((1 + 2) + 3)) = (4 + ((3) + 3)) = (4 + (6)) = (10) (4+((1+2)+3))=(4+((3)+3))=(4+(6))=(10)
有三个中间和是 3 , 6 , 10 3,6,10 3,6,10 ,它们之和为 3 + 6 + 10 = 19 3 + 6 + 10 = 19 3+6+10=19


输入格式

第一行输入一个整数 n n n,表示 a a a 元素个数。
第二行输入 n n n 个整数 a i a_i ai

输出格式

第一行输出添加括号的方法。
第二行输出最终的中间和之和。
第三行输出 n − 1 n - 1 n1 个中间和,按照从里到外,从左到右的顺序输出。

样例

样例输入1:

4
4 1 2 3

样例输出1:

(4+((1+2)+3))
19
3 6 10

样例解释见上。

数据范围

1 ≤ n ≤ 20 1 \le n \le 20 1n20
1 ≤ a i ≤ 100 1 \le a_i \le 100 1ai100

题解

+ + + 看成合并左右两个元素, ( ) () () 限定合并顺序。

按照正常的 区间dp ,很容易计算出中间和之和。


那如何输出算式和每个中间和呢?

当把区间 i , k i, k i,k k + 1 , j k + 1, j k+1,j 合并成 i , j i, j i,j 时,记录 k − i k - i ki 的值(合并位置 d i , j d_{i, j} di,j)。
然后写一个 dfs,传两个参数 l l l r r r,表示 l l l r r r 的区间。

  • 如果 l ≥ r l \ge r lr,返回。
  • 如果 l < r l < r l<r,将 l l l r r r 的区间拆分为两个区间进行 dfs l l l l + d i , j l + d_{i, j} l+di,j l + d i , j + 1 l + d_{i, j} + 1 l+di,j+1 r r r),并将 l l l 的左括号数( f 1 l f1_l f1l)加 1 1 1 r r r 的右括号数( f 2 r f2_r f2r)加 1 1 1

接下来从 1 1 1 n n n 输出,先输出 f 1 i f1_i f1i 个左括号,再输出 a i a_i ai,然后输出 f 2 i f2_i f2i 个右括号。如果 i ≠ n i \ne n i=n,还要输出 + + +

这样就能轻松地输出算式了。

输出中间和也是同理,可用前缀和优化。

int f[40][40];//dp
int sum[40];//前缀和
int d[40][40];//从 i 到 j 合并的点
int f1[40], f2[40];//左括号数和右括号数
//算式
void dfs(int x, int y){if(x >= y){return;}dfs(x, x + d[x][y]);dfs(x + d[x][y] + 1, y);f1[x] ++;f2[y] ++;
}
//中间和
void dfs2(int x, int y){if(x >= y){return;}dfs2(x, x + d[x][y]);dfs2(x + d[x][y] + 1, y);printf("%d ", sum[y] - sum[x - 1]);
}
int main(){输入//初始化memset(f, 0x3f, sizeof(f)))memset(d, 0, sizeof(d));for(int i = 1; i <= n; ++ i){f[i][i] = 0;}//前缀和for(int i = 1; i <= n; ++ i){sum[i] = sum[i - 1] + a[i];}for(int k = 1; k < n; ++ k){for(int i = 1; i <= n - k; ++ i){int j = i + k;for(int u = i; u < j; ++ u){//更新 f[i][j]if(f[i][j] > f[i][u] + f[u + 1][j]){f[i][j] = f[i][u] + f[u + 1][j];d[i][j] = u - i;}}f[i][j] += sum[j] - sum[i - 1];}}//输出 dfs(1, n); for(int i = 1; i <= n; ++ i){while(f1[i]{putchar('(');f1[i] --;}printf("%d", a[i]);while(f2[i]){putchar(')');f2[i] --;}if(i != n){putchar('+');}}printf("\n%d\n", f[1][n]);dfs2(1, n)return 0;
}

禁止抄袭!!!

相关文章:

[区间dp]添加括号

题目描述 有一个 n n n 个元素的数组 a a a。不改变序列中每个元素在序列中的位置&#xff0c;把它们相加&#xff0c;并用括号记每次加法所得的和&#xff0c;称为中间和。现在要添上 n − 1 n - 1 n−1 对括号&#xff0c;加法运算依括号顺序进行&#xff0c;得到 n − …...

jenkins流水线+k8s部署springcloud微服务架构项目

文章目录 1.k8s安装2.jenkins安装3.k8s重要知识1.简介2.核心概念3.重要命令1.查看集群消息2.命名空间3.资源创建/更新4.资源查看5.描述某个资源的详细信息6.资源编辑7.资源删除8.资源重启9.查看资源日志10.资源标签 4.k8s控制台1.登录2.界面基本操作1.选择命名空间2.查看命名空…...

安卓开发板_联发科MTK开发评估套件串口调试

串口调试 如果正在进行lk(little kernel ) 或内核开发&#xff0c;USB 串口适配器&#xff08; USB 转串口 TTL 适配器的简称&#xff09;对于检查系统启动日志非常有用&#xff0c;特别是在没有图形桌面显示的情况下。 1.选购适配器 常用的许多 USB 转串口的适配器&#xf…...

vue+el-table 可输入表格使用上下键进行input框切换

使用上下键进行完工数量这一列的切换 <el-table :data"form.detailList" selection-change"handleChildSelection" ref"bChangeOrderChild" max-height"500"><!-- <el-table-column type"selection" width&quo…...

中国书法——孙溟㠭浅析碑帖《三希堂法帖》

孙溟㠭浅析碑帖《三希堂法帖》 全称是《三希堂石渠宝笈法帖》&#xff0c;是中国清代宫廷刻帖&#xff0c;一共三十二册。 清朝高宗弘历收藏了晋王羲之《快雪时晴帖》&#xff0c;王献之的《中秋帖》&#xff0c;王珣的《伯远帖》三种王氏原墨迹。故而把所藏法书之所…...

深入探讨生成对抗网络(GANs):颠覆传统的AI创作方式

在人工智能的快速发展中&#xff0c;生成对抗网络&#xff08;Generative Adversarial Networks, GANs&#xff09;无疑是一个引人注目的技术。自2014年由Ian Goodfellow等人首次提出以来&#xff0c;GANs已经在图像生成、文本生成、视频生成等多个领域展现出了惊人的能力。本文…...

vmware Vnet8虚拟网卡丢失的找回问题

vmware Vnet8虚拟网卡丢失的找回问题 1.打开VMware Workstation 2.然后点击Edit --> Virtual Network Edit --> 打开Virtual Network Edit框 &#xff0c; 3.点击最下面的的Restore Default 按钮&#xff0c; 3.恢复默认设置&#xff0c;这会在网络连接那块可以看到丢失…...

Python 从入门到实战13(字符串简介)

我们的目标是&#xff1a;通过这一套资料学习下来&#xff0c;通过熟练掌握python基础&#xff0c;然后结合经典实例、实践相结合&#xff0c;使我们完全掌握python&#xff0c;并做到独立完成项目开发的能力。 上篇文章我们通过举例学习了流程控制语句中的循环语句。今天继续讨…...

Redis_RDB持久化

基于RDB的持久化方式会把当前内存中所有的redis键值对数据以快照的方式写入硬盘文件中&#xff0c;如果需要恢复数据&#xff0c;就把快照文件读到内存中。 RDB快照文件是经压缩的二进制格式的文件&#xff0c;它的储存路径不仅可以在redis服务器启动前通过配置参数来设置&…...

SOP流程制定:vioovi ECRS工时分析软件的智慧引领

在现代制造业中&#xff0c;标准化操作流程&#xff08;SOP&#xff09;已成为提升生产效率、确保产品质量、降低运营成本的关键要素。SOP不仅为生产活动提供了明确的指导&#xff0c;还促进了企业管理的规范化和精细化。然而&#xff0c;如何科学、高效地制定SOP流程&#xff…...

并发编程-synchronized解决原子性问题

并发编程-synchronized解决原子性问题 文章目录 并发编程-synchronized解决原子性问题零、说在前面一、线程安全问题1.1 什么是线程安全问题1.2 自增运算不是线程安全的1.3 临界区资源与临界区代码段 二、synchronized 关键字的使用2.1 synchronized 关键字作用2.2 synchronize…...

CSS之我不会

非常推荐html-css学习视频&#xff1a;尚硅谷html-css 一、选择器 作用&#xff1a;选择页面上的某一个后者某一类元素 基本选择器 1.标签选择器 格式&#xff1a;标签{} <h1>666</h1><style>h1{css语法} </style>2.类选择器 格式&#xff1a;.类…...

AI绘画:SD打光神器!(Stable Diffusion进阶篇:Imposing Consistent Light)

前言 在上一篇笔记中学习了如何简单地下载以及使用IC-Light&#xff0c;今天的内容会稍微有点不一样。 对于学过stable diffusion的小伙伴来说&#xff0c;forge UI和Comfy UI会更加熟悉一些。在IC-Light发布后&#xff0c;Openpose editor的开发者将其制作成了一个Forge UI上…...

QQ频道机器人零基础开发详解(基于QQ官方机器人文档)[第二期]

QQ频道机器人零基础开发详解(基于QQ官方机器人文档)[第二期] 第二期介绍&#xff1a;频道模块之频道管理 目录 QQ频道机器人零基础开发详解(基于QQ官方机器人文档)[第二期]第二期介绍&#xff1a;频道模块之频道管理获取用户详情获取用户频道列表获取频道详情获取子频道列表获…...

参赛心得和思路分享:2021第二届云原生编程挑战赛2: 实现一个柔性集群调度机制

关联比赛: 2021第二届云原生编程挑战赛2&#xff1a;实现一个柔性集群调度机制 参赛心得 历时快两个月的第二届云原生编程挑战赛结束了&#xff0c;作为第一次参赛的萌新&#xff0c;拿下了28名的成绩&#xff0c;与第一名差了19万分&#xff0c;因为赛制时间太长&#xff0c…...

具体函数的卡诺图填入

目录 用卡诺图表示逻辑函数 基本步骤 例子1 例子2 例子3 用卡诺图表示逻辑函数 基本步骤 例子1 由真值表得卡诺图。 在函数值为1的地方在卡诺图上画上1。 例子2 例子3 非标准与或式&#xff0c;要找到公共部分。 将AB所在的那一行填上1。 将A非D的那个部分也填上1。 再…...

STM32 HAL freertos零基础(六)计数型信号量

1、计数型信号量 计数型信号量(Counting Semaphore)是另一种类型的信号量,它可以保持一个大于等于0的整数值,这个值表示可用资源的数量。本质上相当于队列长度大于1得队列。经典问题就是剩余车辆统计,出入车辆,车辆数据可以实时更新。 2、相关API函数 xSemaphoreCreat…...

Dynamics CRM Ribbon Workbench-the solution contains non-entity components

今天在一个低版本的环境里准备用Ribbon Workbench去编辑一个按钮时&#xff0c;遇到了如下错误 一开始没当回事&#xff0c;以为是我的解决方案问题&#xff0c;去检查了下&#xff0c;只有一个组件&#xff0c;并且哪怕我把组件换成了某个实体也不行&#xff0c;尝试了其他任何…...

谷歌对抗司法部:为什么谷歌的“数百个竞争对手”说法站不住脚

随着谷歌反垄断陪审团审判的进行&#xff0c;谷歌声称美国司法部对广告技术市场的看法狭隘&#xff0c;并且广告商和出版商有很多替代选择。然而&#xff0c;证据并不支持这一说法。 谷歌误导性地声称有“数百个竞争对手。” 虽然存在许多广告技术提供商&#xff0c;但谷歌在…...

重生奇迹MU 沉迷升级的快感 法魔升级机器人

重生奇迹MU是一款以升级为主要玩法的游戏。升级是游戏基础&#xff0c;也是最重要的部分。通过升级&#xff0c;玩家可以获得更多的基础属性奖励和自由点数奖励&#xff0c;同时还能够穿戴最好的装备和翅膀。因此&#xff0c;升级在游戏中具有极其重要的地位。 史上升级最快的…...

ubuntu搭建nfs服务centos挂载访问

在Ubuntu上设置NFS服务器 在Ubuntu上&#xff0c;你可以使用apt包管理器来安装NFS服务器。打开终端并运行&#xff1a; sudo apt update sudo apt install nfs-kernel-server创建共享目录 创建一个目录用于共享&#xff0c;例如/shared&#xff1a; sudo mkdir /shared sud…...

uni-app学习笔记二十二---使用vite.config.js全局导入常用依赖

在前面的练习中&#xff0c;每个页面需要使用ref&#xff0c;onShow等生命周期钩子函数时都需要像下面这样导入 import {onMounted, ref} from "vue" 如果不想每个页面都导入&#xff0c;需要使用node.js命令npm安装unplugin-auto-import npm install unplugin-au…...

Linux简单的操作

ls ls 查看当前目录 ll 查看详细内容 ls -a 查看所有的内容 ls --help 查看方法文档 pwd pwd 查看当前路径 cd cd 转路径 cd .. 转上一级路径 cd 名 转换路径 …...

工程地质软件市场:发展现状、趋势与策略建议

一、引言 在工程建设领域&#xff0c;准确把握地质条件是确保项目顺利推进和安全运营的关键。工程地质软件作为处理、分析、模拟和展示工程地质数据的重要工具&#xff0c;正发挥着日益重要的作用。它凭借强大的数据处理能力、三维建模功能、空间分析工具和可视化展示手段&…...

如何将联系人从 iPhone 转移到 Android

从 iPhone 换到 Android 手机时&#xff0c;你可能需要保留重要的数据&#xff0c;例如通讯录。好在&#xff0c;将通讯录从 iPhone 转移到 Android 手机非常简单&#xff0c;你可以从本文中学习 6 种可靠的方法&#xff0c;确保随时保持连接&#xff0c;不错过任何信息。 第 1…...

《基于Apache Flink的流处理》笔记

思维导图 1-3 章 4-7章 8-11 章 参考资料 源码&#xff1a; https://github.com/streaming-with-flink 博客 https://flink.apache.org/bloghttps://www.ververica.com/blog 聚会及会议 https://flink-forward.orghttps://www.meetup.com/topics/apache-flink https://n…...

Reasoning over Uncertain Text by Generative Large Language Models

https://ojs.aaai.org/index.php/AAAI/article/view/34674/36829https://ojs.aaai.org/index.php/AAAI/article/view/34674/36829 1. 概述 文本中的不确定性在许多语境中传达,从日常对话到特定领域的文档(例如医学文档)(Heritage 2013;Landmark、Gulbrandsen 和 Svenevei…...

Linux C语言网络编程详细入门教程:如何一步步实现TCP服务端与客户端通信

文章目录 Linux C语言网络编程详细入门教程&#xff1a;如何一步步实现TCP服务端与客户端通信前言一、网络通信基础概念二、服务端与客户端的完整流程图解三、每一步的详细讲解和代码示例1. 创建Socket&#xff08;服务端和客户端都要&#xff09;2. 绑定本地地址和端口&#x…...

Java编程之桥接模式

定义 桥接模式&#xff08;Bridge Pattern&#xff09;属于结构型设计模式&#xff0c;它的核心意图是将抽象部分与实现部分分离&#xff0c;使它们可以独立地变化。这种模式通过组合关系来替代继承关系&#xff0c;从而降低了抽象和实现这两个可变维度之间的耦合度。 用例子…...

代码规范和架构【立芯理论一】(2025.06.08)

1、代码规范的目标 代码简洁精炼、美观&#xff0c;可持续性好高效率高复用&#xff0c;可移植性好高内聚&#xff0c;低耦合没有冗余规范性&#xff0c;代码有规可循&#xff0c;可以看出自己当时的思考过程特殊排版&#xff0c;特殊语法&#xff0c;特殊指令&#xff0c;必须…...