合并石子 | 第十四届蓝桥杯省赛JavaB组
在桌面从左至右横向摆放着 N 堆石子。
每一堆石子都有着相同的颜色,颜色可能是颜色 0,颜色 1 或者颜色 2 中的其中一种。
现在要对石子进行合并,规定每次只能选择位置相邻并且颜色相同的两堆石子进行合并。
合并后新堆的相对位置保持不变,新堆的石子数目为所选择的两堆石子数目之和,并且新堆石子的颜色也会发生循环式的变化。
具体来说:两堆颜色 0 的石子合并后的石子堆为颜色 1,两堆颜色 1 的石子合并后的石子堆为颜色 2,两堆颜色 2 的石子合并后的石子堆为颜色 0。
本次合并的花费为所选择的两堆石子的数目之和。
给出 N 堆石子以及他们的初始颜色,请问最少可以将它们合并为多少堆石子?
如果有多种答案,选择其中合并总花费最小的一种,合并总花费指的是在所有的合并操作中产生的合并花费的总和。
输入格式
第一行一个正整数 N 表示石子堆数。
第二行包含 N 个用空格分隔的正整数,表示从左至右每一堆石子的数目。
第三行包含 N 个值为 0 或 1 或 2的整数表示每堆石头的颜色。
输出格式
一行包含两个整数,用空格分隔。
其中第一个整数表示合并后数目最少的石头堆数,第二个整数表示对应的最小花费。
数据范围
对于 30% 的评测用例,1≤N≤10。
对于 50% 的评测用例,1≤N≤50。
对于 100% 的评测用例,1≤N≤300,1≤ 每堆石子的数目 ≤1000。
输入样例:
5
5 10 1 8 6
1 1 0 2 2
输出样例:
2 44
样例解释
上图显示了两种不同的合并方式。
其中节点中标明了每一堆的石子数目,在方括号中标注了当前堆石子的颜色属性。
左图的这种合并方式最终剩下了两堆石子,所产生的合并总花费为 15+14+15=44;右图的这种合并方式最终也剩下了两堆石子,但产生的合并总花费为 14+15+25=54。
综上所述,我们选择合并花费为 44 的这种方式作为答案。
题解:
使用区间DP,f[i][j][k]代表区间i-j之间颜色为k的合法情况,初始状态当i==j的时候,除自身颜色为0,即f[i][j][k]=0,其他为INF。
c[i][j]代表区间i-j之间能合并的最小堆数。
w[i][j]代表区间i-j之间的最小价值。
s[i]使用前缀和代表每个堆的价值以及区间的价值。
遍历长度,找出左边界和右边界,遍历区间,遍历颜色,当遇到左和右颜色相同的时候,合并,将c[i][j]设置为0,只有一个堆,重新赋值颜色以及合并后的价值。
注意:这里要重新循环一遍来更新最小的堆数和价值。
(代码参考了大佬的)
代码:
AC代码:
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<iomanip>
#include<queue>
#include<stack>
#include<vector>
#include<unordered_set>
#include<unordered_map>
#include<map>
#include<set>
using namespace std;
typedef long long int ll;
const int INF=1e16;int n=0;
int minsize=1000001;
int minvalue=1000001;int change_color(int c){if(c==1){return 2;}else if(c==2){return 0;}else if(c==0){return 1;}
}void solve(int n){int c[305][305];int w[305][305];int v[305][305];int f[305][305][3];int s[305];//初始化for(int i=1;i<=n;i++){for(int j=i;j<=n;j++){c[i][j]=j-i+1;if(i!=j){w[i][j]=INF;}for(int k=0;k<3;k++){f[i][j][k]=INF;}}}for(int i=1;i<=n;i++){int t;cin >> t;s[i]=s[i-1]+t;}for(int i=1;i<=n;i++){int t;cin >> t;f[i][i][t]=0;}for(int len=1;len<=n;len++){for(int l=1;l+len-1<=n;l++){int r=l+len-1;for(int i=0;i<3;i++){int a=INF;for(int j=l;j<r;j++){if(f[l][j][i]!=INF && f[j+1][r][i]!=INF){a=min(a,f[l][j][i]+f[j+1][r][i]);}}if(a!=INF){c[l][r]=1;f[l][r][(i+1)%3]=min(f[l][r][(i+1)%3],a+s[r]-s[l-1]);w[l][r]=min(w[l][r],f[l][r][(i+1)%3]);}}for(int j=l;j<r;j++){if(c[l][r]>c[l][j]+c[j+1][r]){c[l][r]=c[l][j]+c[j+1][r];w[l][r]=w[l][j]+w[j+1][r];}else if(c[l][r]==c[l][j]+c[j+1][r]){w[l][r]=min(w[l][r],w[l][j]+w[j+1][r]);}}}}cout<<c[1][n]<<' '<<w[1][n];
}int main(){cin >> n;solve(n);//cout << minsize << " " << minvalue;
}
TLE代码:
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<iomanip>
#include<queue>
#include<stack>
#include<vector>
#include<unordered_set>
#include<unordered_map>
#include<map>
#include<set>
using namespace std;
typedef long long int ll;int n=0;
int minsize=1000001;
int minvalue=1000001;int change_color(int c){if(c==1){return 2;}else if(c==2){return 0;}else if(c==0){return 1;}
}void dfs(int now,int now_value,int n,vector<int> v,vector<int> c){//checkif(now==c.size()-1){//cout << c.size() << " " << now_value << "\n";if(c.size()<minsize){minsize=c.size();minvalue=now_value;}else if(c.size()==minsize && now_value<minvalue){minvalue=now_value;}return;}//nodfs(now+1,now_value,n,v,c);//yesif(now<c.size()-1 && c[now]==c[now+1]){int value=v[now]+v[now+1];int color=change_color(c[now]);v.erase(v.begin()+now);v.erase(v.begin()+now);c.erase(c.begin()+now);c.erase(c.begin()+now);v.insert(v.begin()+now,value);c.insert(c.begin()+now,color);dfs(0,now_value+value,n,v,c);}
}int main(){cin >> n;vector<int> v;vector<int> c;for(int i=0;i<n;i++){int t;cin >> t;v.push_back(t);}for(int i=0;i<n;i++){int t;cin >> t;c.push_back(t);}dfs(0,0,n,v,c);cout << minsize << " " << minvalue;
}
相关文章:
合并石子 | 第十四届蓝桥杯省赛JavaB组
在桌面从左至右横向摆放着 N 堆石子。 每一堆石子都有着相同的颜色,颜色可能是颜色 0,颜色 1 或者颜色 2 中的其中一种。 现在要对石子进行合并,规定每次只能选择位置相邻并且颜色相同的两堆石子进行合并。 合并后新堆的相对位置保持不变&…...
【商城实战(94)】构建高并发的负载均衡与集群架构
【商城实战】专栏重磅来袭!这是一份专为开发者与电商从业者打造的超详细指南。从项目基础搭建,运用 uniapp、Element Plus、SpringBoot 搭建商城框架,到用户、商品、订单等核心模块开发,再到性能优化、安全加固、多端适配…...
鸿蒙开发:了解Canvas绘制
前言 本文基于Api13 系统的组件无法满足我们的需求,这种情况下就不得不自己自定义组件,除了自定义组合组件,拓展组件,还有一种方式,那就是完全的自绘制组件,这种情况,常见的场景有,比…...
Ubuntu和Windows实现文件互传
1.开启Ubuntu下的FTP服务: (1)终端输入: sudo apt-get install vsftpd(2)安装完成后: 终端输入: /etc 是 Linux 系统的全局配置文件目录,存储系统和应用程序的配置信息…...
dav_pg8_vacuum
一、VACUUM基础概念 1.1 VACUUM的作用 在PostgreSQL中,当数据被更新或删除时,系统并不会立即释放物理空间,而是将其标记为 “可重用”。 随着时间推移,表中的死元组(已删除或已被新版本覆盖的数据)会越来越…...
革新汽车安全通信技术,美格智能全系车载通信模组支持NG-eCall
根据QYR(恒州博智)的统计及预测,2024年全球汽车无线紧急呼叫(eCall)设备市场销售额达到了25.17亿美元,预计2031年将达到44.97亿美元,年复合增长率(CAGR 2025-2031)为8.8%…...
Ubuntu桌面环境下网络设置选项缺失问题解决
一、问题现象 在Ubuntu桌面环境中,网络设置界面中仅显示VPN设置,未显示常规网络配置选项,导致无法通过图形界面修改网络配置。但通过命令行工具可正常设置网络。 二、解决方案 (一)检查网络设备状态 nmcli d 发现…...
GitHub绑定本地计算机以及仓库创建跟推送指南
GitHub绑定到本地计算机 要在本地计算机上连接到你的GitHub账户,可以通过以下步骤实现: 1. 检查和安装Git 确保你的计算机上已经安装了Git。如果还没有安装,可以从Git官网下载并安装。 2. 配置Git 打开终端(macOS或Linux&…...
【数据结构】导航
【数据结构】-CSDN博客 【数据结构】next数组、nextval数组-CSDN博客...
Java内存中的Heap(堆)的作用
Java内存中的Heap(堆)的作用 在 Java 的内存模型中,Heap(堆) 是 JVM(Java Virtual Machine)管理的运行时数据区域之一,主要用于存储程序运行过程中动态分配的对象和数据。它是 Java…...
Python控制结构详解
前言 一、控制结构概述 二、顺序结构 三、选择结构(分支结构) 1. 单分支 if 2. 双分支 if-else 3. 多分支 if-elif-else 4.实际应用: 四、循环结构 1. for循环 2. while循环 3. 循环控制语句 五、异常处理(try-except)…...
2023第十四届蓝桥杯大赛软件赛国赛C/C++ 大学 B 组(真题题解)(C++/Java题解)
本来想刷省赛题呢,结果一不小心刷成国赛了 真是个小迷糊〒▽〒 但,又如何( •̀ ω •́ )✧ 记录刷题的过程、感悟、题解。 希望能帮到,那些与我一同前行的,来自远方的朋友😉 大纲: 一、子2023-ÿ…...
JVM介绍
JVM类加载器 栈指令重排序 类的JVM内存分配 堆内存GC模型...
HTML输出流
HTML 输出流 JavaScript 中**「直接写入 HTML 输出流」**的核心是通过 document.write() 方法向浏览器渲染过程中的数据流动态插入内容。以下是详细解释: 一、HTML 输出流的概念 1. 动态渲染过程 HTML 文档的加载是自上而下逐行解析的。当浏览器遇到 <script&…...
Kafka 的高可用性
Kafka 的高可用性主要通过副本机制、ISR(In-Sync Replicas)列表和控制器 Broker 来实现。这些机制共同确保了 Kafka 集群在部分节点故障时仍然可以正常运行,数据不会丢失,并且服务不会中断。 1. 副本机制 Kafka 的副本机制是其高…...
Centos7,tar包方式部署rabbitmq-3.7.6
1. 环境准备 安装编译工具和依赖包 yum -y install make gcc gcc-c glibc-devel m4 perl openssl openssl-devel ncurses-devel ncurses-devel xz xmlto perl 2. Erlang环境搭建 版本对应:https://www.rabbitmq.com/docs/which-erlang 解压到指定目录 tar -xv…...
RISC-V AIA学习3---APLIC 第二部分(APLIC 中断域的内存映射控制区域)
每个中断域都有一个专用的内存映射控制区域,用来处理该中断域的中断。 控制区域的大小是 4KB 的倍数,对齐到 4KB 边界。最小的有效控制区域是 16KB。 1. 控制区域的基本结构:部门文件柜 每个中断域就像公司的一个部门,有自己的 …...
顶刊【遥感目标检测】【TGRS】FFCA-YOLO遥感图像小目标检测
FFCA-YOLO for Small Object Detection in Remote Sensing Images FFCA-YOLO遥感图像小目标检测 0.论文摘要 摘要——特征表征不足、背景干扰等问题使得遥感图像中的小目标检测任务极具挑战性。尤其在算法需部署于星载设备进行实时处理时,需在有限计算资源下对精度…...
【人工智能】从 Llama 到 DeepSeek:开源大模型的演进与技术对比
《Python OpenCV从菜鸟到高手》带你进入图像处理与计算机视觉的大门! 解锁Python编程的无限可能:《奇妙的Python》带你漫游代码世界 随着人工智能的迅猛发展,开源大语言模型(LLM)在自然语言处理领域扮演着越来越重要的角色。本文从 Meta 的 Llama 系列开始,追溯开源大模…...
【PCB工艺】时序图(Timing Diagram)
时序图(Timing Diagram)是描述数字电路信号随时间变化的图示,广泛用于分析和设计时序逻辑电路,如锁存器(Latch)、触发器(Flip-Flop)、计数器、状态机等。这篇文章从时序图的原理、构…...
MATLAB 中,并行池(Parallel Pool)自动关闭的情况
在 MATLAB 中,并行池(Parallel Pool)的行为可以通过设置进行控制,但默认情况下,并行池不会自动关闭,除非满足某些条件或显式调用关闭命令。以下是关于并行池自动关闭机制的详细说明: 自动关闭的…...
[网安工具] SQL 注入自动探测工具 —— SQLMAP 使用手册
🌟想了解其它网安工具?看看这个:[网安工具] 网安工具库 —— 工具管理手册 https://github.com/sqlmapproject/sqlmaphttps://github.com/sqlmapproject/sqlmap用法 | sqlmap 用户手册https://sqlmap.highlight.ink/usage 0x01:S…...
Python数据结构与算法-基础预热篇
目录 语言基础 1.内置函数 1.1math库 1.2collections 1.2.1Counter:计数器 1.2.2deque双端对列 1.2.3defaultdict有默认值的字典 1.3heapq堆(完全二叉树) 1.4functool 1.5itertools 1.5.1无限迭代器 1.5.2有限迭代器 1.5.3排列组合迭代器 2.序…...
构建可扩展、可靠的网络抓取、监控和自动化应用程序的终极指南
大家好,这里是架构资源栈!点击上方关注,添加“星标”,一起学习大厂前沿架构! 无论您是企业主、营销人员还是软件开发人员,您都很有可能在某个时候使用过 Web 自动化工具。每个人都希望更聪明地工作…...
【蓝桥杯】重点冲刺
【最高优先级】必考核心算法(占分60%以上) 动态规划(DP) 🌟🌟🌟 背包问题:01背包、完全背包(必须掌握空间优化的一维写法) 线性DP:最长上升子序列(LIS)、最长公共子序列(LCS) 路径问题:网格路径计数(含障碍物)、最小路径和 经典模型:打家劫舍、股票买卖问…...
质量工程师的2025:从“找bug“到“造质量“的职业进化
想象一下,2025年的某天:阅读原文 早晨,AI测试助手已经自动运行了夜间回归测试,并将可疑问题标记出来 你喝着咖啡,通过质量数据看板分析系统健康度 下午的会议上,你正用业务语言向产品经理解释:…...
2025年CNG 汽车加气站操作工题目分享
CNG 汽车加气站操作工题目分享: 单选题 1、CNG 加气站中,加气机的加气软管应( )进行检查。 A. 每天 B. 每周 C. 每月 D. 每季度 答案:A 解析:加气软管是加气操作中频繁使用的部件,每天检…...
【QT5 多线程示例】线程池
线程池 【C并发编程】(九)线程池 QThreadPool 和 QRunnable 是 Qt 提供的线程池管理机制。QRunnable 是一个任务抽象类;定义任务逻辑需要继承QRunnable 并实现 run() 方法。QThreadPool 负责管理线程,并将 QRunnable 任务分配到…...
飞致云荣获“Alibaba Cloud Linux最佳AI镜像服务商”称号
2025年3月24日,阿里云云市场联合龙蜥社区发布“2024年度Alibaba Cloud Linux最佳AI镜像服务商”评选结果。 经过主办方的严格考量,飞致云(即杭州飞致云信息科技有限公司)凭借旗下MaxKB开源知识库问答系统、1Panel开源面板、Halo开…...
FAST-LIVO2 Fast, Direct LiDAR-Inertial-Visual Odometry论文阅读
FAST-LIVO2 Fast, Direct LiDAR-Inertial-Visual Odometry论文阅读 论文下载论文翻译FAST-LIVO2: 快速、直接的LiDAR-惯性-视觉里程计摘要I 引言II 相关工作_直接方法__LiDAR-视觉(-惯性)SLAM_ III 系统概述IV 具有顺序状态更新的误差状态迭代卡尔曼滤波…...
kubesphere 终端shell连不上的问题
使用nginx代理kubesphere控制台会出现容器的终端shell连不上的问题 下面是一个样例配置可以解决这个问题: 注意修改为你的ip地址: upstream k8s { ip_hash; server masterip1:30880; server masterip2:30880; server masterip3:30880; } nginx.conf #…...
无人机,雷达定点飞行时,位置发散,位置很飘,原因分析
参考: 无人车传感器 IMU与GPS数据融合进行定位机制_gps imu 组合定位原始数-CSDN博客 我的无人机使用雷达定位,位置模式很飘 雷达的更新频率也是10HZ, 而px飞控的频率是100HZ,没有对两者之间的频率差异做出处理 所以才导致无人…...
外星人入侵(python设计小游戏)
这个游戏简而言之就是操作一个飞机对前方的飞船进行射击,和一款很久之前的游戏很像,这里是超级低配版那个游戏,先来看看效果图: 由于设计的是全屏的,所以电脑不能截图。。。。 下面的就是你操控的飞船,上面…...
Stereolabs ZED Box Mini:NVIDIA Orin™驱动,双GMSL2输入,智能机器视觉AI新选择”
Stereolabs近日推出了ZED Box Mini,这是一款专为视觉AI设计的紧凑型迷你电脑(ECU)。该产品搭载了NVIDIA Orin™系列处理器,具备强大的AI视觉处理能力,适用于机器人、智能基础设施和工业应用等多种场景。ZED Box Mini以…...
IP协议的介绍
网络层的主要功能是在复杂的网络环境中确定一个合适的路径.网络层的协议主要是IP协议.IP协议头格式如下: 1.4位版本号:指定IP协议的版本,常用的是IPV4,对于IPV4来说,这里的值就是4. 2.4位头部长度,单位也是4个字节,4bit表示的最大数字是15,因此IP头部的最大长度就是60字节 3.…...
【入门初级篇】布局类组件的使用(2)
【入门初级篇】布局类组件的使用(2) 视频要点 (1)2分栏场景介绍与实操演示 (2)3分栏场景介绍与实操演示 点击访问myBuilder产品运营平台 CSDN站内资源下载myBuilder 交流请加微信:MyBuilder8…...
高并发金融系统,“可观测-可追溯-可回滚“的闭环审计体系
一句话总结 在高并发金融系统中,审计方案设计需平衡"观测粒度"与"系统损耗",通过双AOP实现非侵入式采集,三表机制保障操作原子性,最终形成"可观测-可追溯-可回滚"的闭环体系。 业务痛点与需求 在…...
(九)Spring Webflux
底层基于Netty实现的Web容器与请求/响应处理机制 参照:Spring WebFlux :: Spring Frameworkhttps://docs.spring.io/spring-framework/reference/6.0/web/webflux.html 一、组件对比 API功能 Servlet-阻塞式Web WebFlux-响应式Web 前端控制器 DispatcherServl…...
如何在Webpack中配置别名路径?
如何在Webpack中配置别名路径? 文章目录 如何在Webpack中配置别名路径?1. 引言2. 配置别名路径的基本原理3. 如何配置别名路径3.1 基本配置3.2 结合Babel与TypeScript3.2.1 Babel配置3.2.2 TypeScript配置 3.3 适用场景与最佳实践 4. 调试与常见问题4.1 …...
office_word中使用宏以及DeepSeek
前言 Word中可以利用DeepSeek来生成各种宏,从而生成我们需要各种数据和图表,这样可以大大减少我们手工的操作。 1、Office的版本 采用的是微软的office2016,如下图: 2、新建一个Word文档 3、开启开发工具 这样菜单中的“开发工具…...
利用GitHub Pages快速部署前端框架静态网页
文章目录 前言GitHub Pages 来部署前端框架(Vue 3 Vite)项目1、配置 GitHub Pages 部署2、将项目推送到 GitHub3、部署到 GitHub Pages4、访问部署页面5、修改代码后的更新部署顺序 前言 可以先参考: 使用 GitHub Pages 快速部署静态网页: …...
前端性能优化思路_场景题
20 万人同时在直播间打赏,前端优化需要考虑高并发、性能优化、流畅体验等问题,涉及 WebSocket 处理、消息去抖、虚拟列表优化、动画优化、CDN 加速 等多个方面。 WebSocket 高并发优化 (1)使用 WebSocket 替代轮询 轮询…...
45 55跳跃游戏解题记录
先是55跳跃游戏,暴力解法会怎样?会超出时间限制,而且有很多细节要注意: func canJump(nums []int) bool {// 处理空数组情况,当nums只剩一个元素时,nums[i:]导致越界。if len(nums) 0 {return false}// 如…...
一个简单的用C#实现的分布式雪花ID算法
雪花ID是一个依赖时间戳根据算法生成的一个Int64的数字ID,一般用来做主键或者订单号等。以下是一个用C#写的雪花ID的简单实现方法 using System; using System.Collections.Concurrent; using System.Diagnostics;public class SnowflakeIdGenerator {// 配置常量p…...
16个气象数据可视化网站整理分享
好的!以下是关于“16个气象数据可视化网站整理分享”的软文: 16个气象数据可视化网站整理分享 气象数据可视化已成为现代气象研究、决策支持以及公众天气服务的重要组成部分。从天气预报到气候变化监测,全球许多气象数据可视化平台为专业人士…...
一周学会Flask3 Python Web开发-SQLAlchemy数据迁移migrate
锋哥原创的Flask3 Python Web开发 Flask3视频教程: 2025版 Flask3 Python web开发 视频教程(无废话版) 玩命更新中~_哔哩哔哩_bilibili 模型类(表)不是一成不变的,当你添加了新的模型类,或是在模型类中添加了新的字段,甚至是修改…...
[原创](Modern C++)现代C++的关键性概念: 如何利用多维数组的指针安全地遍历所有元素
[作者] 常用网名: 猪头三 出生日期: 1981.XX.XX 企鹅交流: 643439947 个人网站: 80x86汇编小站 编程生涯: 2001年~至今[共24年] 职业生涯: 22年 开发语言: C/C、80x86ASM、Object Pascal、Objective-C、C#、R、Python、PHP、Perl、 开发工具: Visual Studio、Delphi、XCode、C …...
本地化智能运维助手:基于 LangChain 数据增强 和 DeepSeek-R1 的K8s运维文档检索与问答系统 Demo
写在前面 博文内容为基于 LangChain 数据增强 和 Ollams 本地部署 DeepSeek-R1实现 K8s运维文档检索与问答系统 Demo通过 Demo 对 LEDVR 工作流, 语义检索有基本认知理解不足小伙伴帮忙指正 😃,生活加油 我看远山,远山悲悯 持续分享技术干货…...
中间件框架漏洞攻略
中间件(英语:Middleware)是提供系统软件和应⽤软件之间连接的软件,以便于软件各部件之间的沟通。 中间件处在操作系统和更⾼⼀级应⽤程序之间。他充当的功能是:将应⽤程序运⾏环境与操作系统隔离,从⽽实…...
在 Ubuntu 上安装 Docker 的完整指南
1. 卸载旧版本(如有) 在安装新版本前,建议先卸载旧版本: sudo apt remove docker docker-engine docker.io containerd runc 2. 安装依赖包 更新软件包索引并安装必要的依赖: sudo apt update sudo apt install -y ca-certificates curl gnupg lsb-release 3. 添加 Do…...