信奥赛CSP-J复赛集训(DP专题)(37):P4170 [CQOI2007] 涂色
信奥赛CSP-J复赛集训(DP专题)(37):P4170 [CQOI2007] 涂色
题目描述
假设你有一条长度为 5 5 5 的木板,初始时没有涂过任何颜色。你希望把它的 5 5 5 个单位长度分别涂上红、绿、蓝、绿、红色,用一个长度为 5 5 5 的字符串表示这个目标: RGBGR \texttt{RGBGR} RGBGR。
每次你可以把一段连续的木板涂成一个给定的颜色,后涂的颜色覆盖先涂的颜色。例如第一次把木板涂成 RRRRR \texttt{RRRRR} RRRRR,第二次涂成 RGGGR \texttt{RGGGR} RGGGR,第三次涂成 RGBGR \texttt{RGBGR} RGBGR,达到目标。
用尽量少的涂色次数达到目标。
输入格式
输入仅一行,包含一个长度为 n n n 的字符串,即涂色目标。字符串中的每个字符都是一个大写字母,不同的字母代表不同颜色,相同的字母代表相同颜色。
输出格式
仅一行,包含一个数,即最少的涂色次数。
输入输出样例 #1
输入 #1
AAAAA
输出 #1
1
输入输出样例 #2
输入 #2
RGBGR
输出 #2
3
说明/提示
40 % 40\% 40% 的数据满足 1 ≤ n ≤ 10 1\le n\le 10 1≤n≤10。
100 % 100\% 100% 的数据满足 1 ≤ n ≤ 50 1\le n\le 50 1≤n≤50。
AC代码:
#include<bits/stdc++.h>
using namespace std;char s[60]; // 存储输入的字符串
int dp[60][60]; // dp[l][r]表示将区间[l..r]涂成目标颜色所需的最少次数int main(){scanf("%s", s + 1); // 从s[1]开始读取字符串int n = strlen(s + 1); // 获取字符串长度memset(dp, 0x3f, sizeof(dp)); // 初始化为极大值,表示不可达// 初始化单个字符的情况for(int i = 1; i <= n; i++){dp[i][i] = 1; // 单个字符只需涂一次}// 动态规划处理所有区间for(int k = 2; k <= n; k++){ // 枚举区间长度,从2到nfor(int l = 1; l + k - 1 <= n; l++){ // 枚举区间左端点lint r = l + k - 1; // 计算区间右端点r// 如果区间两端字符相同,则可能合并涂色if(s[l] == s[r]){dp[l][r] = min(dp[l + 1][r], dp[l][r - 1]); // 取不包含左端点或不包含右端点的子区间的最小值}// 遍历所有可能的分割点,寻找更优解for(int i = l; i < r; i++){dp[l][r] = min(dp[l][r], dp[l][i] + dp[i + 1][r]);}}}printf("%d\n", dp[1][n]); // 输出整个字符串的最少涂色次数return 0;
}
功能分析:
该程序采用动态规划解决区间涂色问题,关键点如下:
-
状态定义:
dp[l][r]
表示将区间[l..r]
涂成目标颜色所需的最少次数。 -
初始化:每个单字符区间
dp[i][i]
初始化为1,因为只需一次涂色。 -
状态转移:
- 两端相同处理:若区间两端字符相同,则
dp[l][r]
可取左右子区间的最小值,因为可以在涂色时覆盖端点。 - 分割点遍历:枚举所有可能的分割点
i
,将区间分为[l..i]
和[i+1..r]
,取两部分次数和的最小值。
- 两端相同处理:若区间两端字符相同,则
-
自底向上计算:从小区间逐步求解大区间,确保每个区间的解都基于最优子结构。
-
复杂度:时间复杂度为O(n³),适用于题目中的n≤50的数据范围。
文末彩蛋:
关注并查看老师的个人主页,学习完整csp信奥赛完整系列课程: https://edu.csdn.net/lecturer/7901
相关文章:
信奥赛CSP-J复赛集训(DP专题)(37):P4170 [CQOI2007] 涂色
信奥赛CSP-J复赛集训(DP专题)(37):P4170 [CQOI2007] 涂色 题目描述 假设你有一条长度为 5 5 5 的木板,初始时没有涂过任何颜色。你希望把它的 5 5 5 个单位长度分别涂上红、绿、蓝、绿、红色,…...
代码随想录算法训练营第五十六天| 图论2—卡码网99. 岛屿数量(dfs bfs)
假期归来继续刷题,图论第二天,主要是进一步熟悉dfs 和 bfs 的运用。 99. 岛屿数量(dfs) 99. 岛屿数量 ACM模式还是需要练,不过现在输入输出的感觉已经比较熟悉了。首先是要按照输入搭建一个grid,然后有一…...
iOS开发架构——MVC、MVP和MVVM对比
文章目录 前言MVC(Model - View - Controller)MVP(Model - View - Presenter)MVVM(Model - View - ViewModel) 前言 在 iOS 开发中,MVC、MVVM、和 MVP 是常见的三种架构模式,它们主…...
雅思阅读--易错词汇60个
文章目录 5. pretty6. matterIt does not matter ...7. stage8. draw... draw attention ...5. pretty 23个大满贯单打冠军,传奇网球运动员 WIlliams 曾经说过: I’ve always been pretty confident in my abilities. 翻译:我一直对自己的能力很有信心。 分析:在本句中,“…...
精益数据分析(44/126):深度解析媒体网站商业模式的关键要点
精益数据分析(44/126):深度解析媒体网站商业模式的关键要点 在创业与数据分析的探索道路上,我们不断挖掘不同商业模式的核心要素,今天将深入剖析媒体网站商业模式。希望通过对《精益数据分析》相关内容的解读…...
【回眸】QAC使用指南——导出 Dashboard Report个性化定制Report
前言 按错误级别导出Dashboard的报告 导出Dashboard个性化定制报告 添加个性化设计 导出个性化报告(HTML/PDF/XML) 过滤级别错误 后记 前言 QAC除了导出常规的报告之外,还可以导出Dashboard的报告(XML格式或者PDF格式&…...
高铁座位指示灯系统技术深度解析:从物联网到智慧出行的实践路径
摘要 高铁座位指示灯系统作为铁路数字化转型的核心场景,通过物联网、实时数据同步等技术,实现了客票系统与列车座位状态的动态联动。本文结合权威技术文档与现场实践,从系统架构、数据交互、工程实现等维度展开深度解析,并探讨其…...
ReSearch:强化学习赋能大模型,推理与搜索的创新融合
ReSearch:强化学习赋能大模型,推理与搜索的创新融合 大语言模型(LLMs)的推理能力不断提升,却在与外部搜索结合处理复杂问题时遇阻。本文提出的ReSearch框架,借助强化学习让LLMs学会将搜索融入推理…...
python的selenium操控浏览器
咱们以操控谷歌浏览器为例子 各系统谷歌浏览器及其工具最新版本下载地址 Chrome for Testing availability 查看谷歌浏览器版本 设置->关于Chrome->查看当前谷歌浏览器版本 下载与谷歌浏览器版本对应的chromedriver 注意:与谷歌浏览器版本一模一样的不一定…...
1、PLC控制面板 - /自动化与控制组件/plc-control-panel
76个工业组件库示例汇总 PLC控制系统监控面板 这是一个用于PLC控制系统监控面板的自定义组件,提供了PLC编程与自动化控制逻辑设计的可视化监控界面。组件采用工业风格设计,包含实时数据展示、系统状态监控、控制功能以及报警和日志记录等功能。 功能特…...
LeetCode 热题 100 279. 完全平方数
LeetCode 热题 100 | 279. 完全平方数 大家好,今天我们来解决一道经典的动态规划问题——完全平方数。这道题在 LeetCode 上被标记为中等难度,要求找到和为给定整数 n 的完全平方数的最少数量。 问题描述 给定一个整数 n,返回和为 n 的完全…...
USB学习【2】通讯的基础-反向不归零编码
一.写在前面 所有的通讯协议,发送端和接收端必须按照同一节奏发送信号和接受信号才能保证通讯的正常进行,否则会出现错位。 这个节奏用我自己的话说:时间卡尺。 串口协议是通过约定好波特率来进行解析信号。IIC是专门有一个时钟线作为时间卡…...
Polygon Miden网络:具有客户端执行的边缘区块链
1. 引言 LambdaClass与Miden已合作超过18个月,这段合作关系始于帮助 Miden 开发客户端,为 Miden 网络提供交易执行和证明的支持。随着时间推移,双方的合作不断加深,工作也扩展到了协议和节点的开发上,涵盖了多个方面。…...
临床智能体AI与环境感知AI的融合:基于python的医疗自然语言处理深度分析
引言 医疗领域的数智化进程正以前所未有的速度推进,人工智能技术的应用尤为显著。随着大型语言模型(LLMs)的迅猛发展,医疗AI已从简单的辅助工具升级为复杂的智能体系统。临床智能体AI与环境感知AI的融合代表了医疗AI的最新发展方向,为重塑医疗运营自然语言处理提供了全新…...
Spring AI Alibaba-03- Spring AI + DeepSeek-R1 + ES/Milvus + RAG 智能对话应用开发全流程
Spring AI Alibaba-03- Spring AI DeepSeek-R1 ES/Milvus RAG 智能对话应用开发全流程 在[人工智能](AI)应用中,模型通常需要访问外部资源或执行特定操作,例如数据库查询、调用外部API或执行计算任务。Spring AI,作…...
20250506异形拼图块(圆形、三角、正方,椭圆/半圆)的中2班幼儿偏好性测试(HTML)
背景介绍 最近在写一份工具运用报告,关于剪纸难度的。所以设计了蝴蝶描边系列和异形凹凸角拼图。 【教学类-102-20】蝴蝶三色图作品2——卡纸蝴蝶“满格变形图”(滴颜料按压对称花纹、原图切边后变形放大到A4横版最大化)-CSDN博客文章浏览阅读609次,点赞8次,收藏3次。【…...
Edge浏览器PDF字体显示错误
Edge浏览器PDF字体显示错误 软件版本信息 Edge Version: 136.0.3240.50 Word Version: Microsoft Office 专业增强版2021问题描述 在Word中使用多级列表自动编号, 并使用Word软件自带的导出为PDF文件功能, 在Word中显示正常的数字, 在Edge中查看PDF将会出现渲染错误的现象,…...
git中android studio不想提交文件
修改.gitignore文件 *.iml .gradle /local.properties /.idea/caches /.idea/libraries /.idea/modules.xml /.idea/workspace.xml /.idea/navEditor.xml /.idea/assetWizardSettings.xml /.idea/* /app/* .DS_Store /build /captures .externalNativeBuild .cxx local.propert…...
==和equals的区别 hashCode和equals的联系
和equals的区别: 对于没有重写equals()方法的类,和equals的作用是相同的:比较两个实例对象的地址是否相同。而对于重写了equals方法的类,equals方法则比较的是两个实例对象的内容(例如String对象)。 hashC…...
国联股份卫多多与国术科技签署战略合作协议
4月30日,国术科技(北京)有限公司(以下简称“国术科技”)营销中心总经理 王志广、贾雷一行到访国联股份卫多多,同卫多多/纸多多副总裁、产发部总经理段任飞,卫多多机器人产业链总经理桂林展开深入…...
依图科技C++后端开发面试题及参考答案
请介绍你所了解的分布式系统 分布式系统是由多个独立的计算节点通过网络连接组成的系统,这些节点共同协作以完成特定的任务。分布式系统的设计目标在于提升系统的性能、可扩展性、可靠性和容错性。 从性能方面来看,分布式系统能够把任务分配到多个节点…...
【计算机网络】TCP/IP四层模型是什么?与OSI七层模型哪些区别?
TCP/IP四层模型从上到下依次为: 1.应用层 2.传输层 3.网络层 4.网络接口层 一、TCP/IP四层模型: 1.应用层: 提供用户可直接使用的网络服务。如网页、邮件。 关键协议: HTTP/HTTPS:网页浏览。DNS:域名解…...
基于计算机视觉的试卷答题区表格识别与提取技术
基于计算机视觉的试卷答题区表格识别与提取技术 摘要 本文介绍了一种基于计算机视觉技术的试卷答题区表格识别与提取算法。该算法能够自动从试卷图像中定位答题区表格,执行图像方向矫正,精确识别表格网格线,并提取每个答案单元格。本技术可…...
Java面试全栈解析:Spring Boot、Kafka与Redis实战揭秘
《Java面试全栈解析:Spring Boot、Kafka与Redis实战揭秘》 【面试现场】 面试官:(推了推眼镜)小张,你简历里提到用Spring Boot开发过微服务系统,能说说自动配置的实现原理吗? 程序员࿱…...
打成jar 包以后,运行时找不到文件路径?
报错信息: FileNotFoundException。。。。。。。 原因: 打成jar包后,路径src/*可能都找不到了。 使用命令,查看jar包内的结构及文件路径: tar -tf XX.jar 你会看到目录结构: META-INF/ META-INF/MANIFEST.MF main/ ma…...
C++复习2
set、map、multiset、multimap CSTL包含了序列式容器和关联式容器: 序列式容器里面存储的是元素本身,其底层为线性序列的数据结构。比如:vector,list,deque,forward_list(C11)等。 关联式容器里面存储的是…...
el-row el-col
参考layout布局 Element - The worlds most popular Vue UI frameworkElement,一套为开发者、设计师和产品经理准备的基于 Vue 2.0 的桌面端组件库https://element.eleme.cn/#/zh-CN/component/layout#row-attributes 一行可以看做24个 Element UI 中的 el-row 是…...
【旅游网站设计与实现】基于SpringBoot + Vue 的前后端分离项目 | 万字详细文档 + 源码 + 数据库 + PPT
一、项目简介 旅游网站管理系统以信息化为核心,结合用户体验和系统管理功能,为旅游爱好者和管理者提供全面的服务平台。通过系统,用户可以浏览线路、收藏心仪旅游产品、下单订购,管理员则可在后台完成旅游线路管理、用户管理、订…...
On the Biology of a Large Language Model——论文学习笔记——拒答和越狱
本文仍然是对Anthropic团队的模型解释工作 On the Biology of a Large Language Model 的学习笔记。 前几篇课见我的主页中相同标题的几篇文章 本篇主要关注的是该博客中的Refusal和 Life of a Jailbreak这两部分的内容。 一句话总结 在这两部分中,作者展示了以下…...
使用OpenCV 和Dlib 实现表情识别
文章目录 引言1.代码主要概述2.代码解析2.1 面部特征计算函数(1) 嘴部宽高比(MAR)(2) 嘴宽与脸颊宽比值(MJR)(3) 眼睛纵横比(EAR)(4) 眉毛弯曲比(EBR) 2.2 自定义函数显示中文2.3 表情分类逻辑2.4 实时视频处理 3.系统特点4.总结 引言 面部表情是人类情感交流的重要方式&#…...
Matplotlib 饼图
pie():绘制饼图 Matplotlib 直方图 我们也可以结合 Pandas 来绘制直方图 除了数据框之外,我们还可以使用 Pandas 中的 Series 对象绘制直方图。只需将数据框中的列替换为 Series 对象 Matplotlib imshow() imshow() 可以显示灰度图像 imshow() 可以显示彩…...
区块链交易所开发:开启数字交易新时代
区块链交易所开发:开启数字交易新时代 ——2025年技术革新与万亿级市场的破局指南 一、区块链交易所的颠覆性价值 1️⃣ 去中心化革命终结数据霸权 区块链交易所通过分布式账本技术,将交易数据存储于全网节点,彻底消除中心化服务器宕机、跑路…...
ChatGPT对话导出工具-轻松提取聊天记录导出至本地[特殊字符]安装指南
1、edge浏览器安装tampermonkey插件 Edge浏览器安装:https://microsoftedge.microsoft.com/addons/detail/%E7%AF%A1%E6%94%B9%E7%8C%B4/iikmkjmpaadaobahmlepeloendndfphd 其他浏览器安装:https://www.tampermonkey.net/index.php?browserchrome 2、…...
k8s node soft lockup (内核软死锁) 优化方案
在 Kubernetes 环境中,Node 节点的内核软死锁(soft lockup)是一个严重的稳定性问题,可能导致节点无响应、Pod 调度失败甚至数据丢失。以下是针对该问题的优化策略和解决方案: 一、临时缓解措施 1. 调整内核 watchdog…...
【LDM】视觉自回归建模:通过Next-Scale预测生成可扩展图像(NeurIPS2024最佳论文阅读笔记与吃瓜)
【LDM】视觉自回归建模:通过Next-Scale预测生成可扩展图像(NeurIPS2024最佳论文阅读笔记与吃瓜) 《Visual Autoregressive Modeling: Scalable Image Generation via Next-Scale Prediction》 视觉自回归建模:通过Next-Scale预测…...
计算机网络-传输层
一、概述 1、逻辑通信:对等层之间的通信好像是沿着水平方向传送的,但两个对等层之间并没有一条水平方向的物理连接。 2、复用与分用 2.1传输层 复用:发送方不同的应用进程可以使用同一传输层协议传送数据 分用:接收方的传输层…...
MacOS+VSCODE 安装esp-adf详细流程
安装python3,省略vscode安装ESP-IDF插件,选择v5.2.5 版本,电脑需要能够访问github,esp-idf安装后的默认目录是: /Users/***/esp/v5.2.5/esp-idf# 启动***为省略名称在/Users/***/esp/ 目录下使用git clone 下载 esp-adf # 国内用…...
2025年5月HCIP题库(带解析)
某个ACL规则如下:则下列哪些IP地址可以被permit规则匹配: rule 5 permit ip source 10.0.2.0 0.0.254.255 A、10.0.4.5 B、10.0.5.6 C、10.0.6.7 D、10.0.2.1 试题答案:A;C;D 试题解析: 10.0.2.000001010.00000000.00000010.0000000…...
【Linux系统】vim编辑器的使用
文章目录 一、vim编辑器的简单介绍二、vim的一键化配置方案(目前只支持 Centos7 x86_64)三、vim编辑器在各模式下的操作1.vim的使用 以及 各模式间的切换2.普通模式(Normal Mode,初始默认处于该模式)3.替换模式&#x…...
网站主机控制面板深度解析:cPanel、Plesk 及其他主流选择
网站主机控制面板深度解析:cPanel、Plesk 及其他主流选择 在网站管理和服务器维护的领域,一个强大且易用的控制面板至关重要。它们能够将复杂的技术命令转化为直观的图形界面,极大简化了网站管理员的工作。本文将为您详细介绍市面上几款主流…...
【程序员AI入门:应用】7.LangChain是什么?
LangChain作为当前最热门的AI应用开发框架,正在重塑大语言模型(LLM)的应用生态。其核心价值在于解耦LLM能力与工程实现,构建起连接智能模型与现实世界的"神经网络"。 一、核心定位:AI应用的"操作系统&q…...
jenkins访问端口调整成80端口
使用 Nginx 反向代理解决以上问题,这样可以: 1. 保持 Jenkins 在其他端口(博主使用8090端口) 稳定运行 2. 通过 Nginx 将 80 端口的请求转发到 Jenkins 3. 更安全,因为 Jenkins 不需要直接监听 80 端口 4. 后续如果…...
如何从服务器日志中分析是否被黑客攻击?
一、关键日志文件定位与攻击特征分析 1. 核心日志文件路径 Web 服务器日志: Nginx:/var/log/nginx/access.log(访问日志)、/var/log/nginx/error.log(错误日志) Apache:/var/log/apache2/…...
[250504] Moonshot AI 发布 Kimi-Audio:开源通用音频大模型,驱动多模态 AI 新浪潮
目录 Moonshot AI 发布 Kimi-Audio:开源音频基础模型,赋能音频理解、生成与对话新时代核心能力与特性技术基础开放资源与评估行业意义 Moonshot AI 发布 Kimi-Audio:开源音频基础模型,赋能音频理解、生成与对话新时代 Moonshot A…...
OpenCV 图形API(77)图像与通道拼接函数-----对图像进行几何变换函数remap()
操作系统:ubuntu22.04 OpenCV版本:OpenCV4.9 IDE:Visual Studio Code 编程语言:C11 算法描述 对图像应用一个通用的几何变换。 函数 remap 使用指定的映射对源图像进行变换: dst ( x , y ) src ( m a p x ( x , y ) , m a p y…...
理清缓存穿透、缓存击穿、缓存雪崩、缓存不一致的本质与解决方案
在构建高性能系统中,缓存(如Redis) 是不可或缺的关键组件,它大幅减轻了数据库压力、加快了响应速度。然而,在高并发环境下,缓存也可能带来一系列棘手的问题,如:缓存穿透、缓存击穿、…...
Jetpack Compose 自定义 Slider 完全指南
自定义 Compose Slider 在 Jetpack Compose 中,你可以通过多种方式自定义 Slider 组件。以下是一些常见的自定义方法: 基本自定义 var sliderPosition by remember { mutableStateOf(0f) }Slider(value sliderPosition,onValueChange { sliderPosit…...
荣耀A8互动娱乐组件部署实录(终章:后台配置系统与整体架构总结)
作者:被配置文件的“开关参数”折磨过无数次的运维兼后端工 一、后台系统架构概述 荣耀A8组件后台采用 PHP 构建,配合 MySQL 数据库与 Redis 缓存系统,整体结构遵循简化版的 MVC 模式。后台主要实现以下核心功能: 系统参数调控与配置热更新 用户管理(封号、授权、角色) …...
本地文件批量切片处理与大模型精准交互系统开发指南
本地文件批量切片处理与大模型精准交互系统开发指南 一、系统架构设计 #mermaid-svg-yCbT2xBukW6iX98y {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-yCbT2xBukW6iX98y .error-icon{fill:#552222;}#mermaid-svg-y…...
homebrew安装配置Python(MAC版)
Mac系统自带python路径为: /System/Library/Frameworks/Python.framework/Versionbrew 安装 Python3 在终端输入以下命令: brew search python3 # 查看支持安装的版本 brew install python3就可以轻松easy安装python了,安装完成后提示 查看 pyth…...