首页 > 试题广场 >

切割 01 串 2.0

[编程题]切割 01 串 2.0
  • 热度指数：179 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
\hspace{15pt}给定一个长度为 n 的 01 串 s。一次切割操作如下：

\hspace{23pt}\bullet\, 选择一个长度 \ge 2 的子串，将其分成两个非空连续子串 a（左）和 b（右）；
\hspace{23pt}\bullet\, 记 a 中字符 0 的出现次数为 C_0，b 中字符 1 的出现次数为 C_1；
\hspace{23pt}\bullet\, 仅当 L\leqq |C_0-C_1|\leqq R 时，此次切割被视为合法。

\hspace{15pt}每次合法切割产生的两个子串都可以继续被独立切割（若长度 \ge 2 且满足切割条件）。问在最优策略下，最多可以执行多少次切割？

输入描述:
\hspace{15pt}第一行输入三个整数 n,L,R\ \bigl(1\leqq n\leqq500,\ 0\leqq L\leqq R\leqq500\bigr)——字符串长度与参数限制。

\hspace{15pt}第二行输入一个长度为 n 的 01 串 s。


输出描述:
\hspace{15pt}输出一个整数，表示最多能执行的切割次数。
示例1

输入

6 2 3
011011

输出

3

说明

其中一种切割次数最多的切法如下：
第一次切割可以切：0\ |\ 11011，然后选择 11011 这个串继续做切割。
第二次切割可以切：1\ |\ 1011，然后选择 1011 这个串继续做切割。
第三次切割可以切：1\ |\ 011。
算法知识视频讲解
开通博客
头像 opeh
发表于 2025-11-16 17:25:10
1.分析 本体就是一个简单的区间dp板子题加了一个判断 2.AC代码 #include<bits/stdc++.h> using namespace std; int main() { int n,L,R; cin>>n>>L>& 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 丨阿伟丨
发表于 2025-09-01 14:16:19
题目描述 给定一个长度为 的 01 串 ，以及两个整数参数 和 。我们可以对任意一个长度大于等于2的子串进行“切割”操作。 一次合法的切割操作定义如下： 选择一个子串，将其分成两个非空的连续子串 （左）和 （右）。 记 中字符 '0' 的出现次数为 ， 中字符 '1' 的出现次数为 。 当且 展开全文
去ta的博客 赞 (0) 回复(0) 收起

问题信息

来自：华为机试编程模拟题7
难度：
0条回答 213浏览

热门推荐

相关试题

切割 01 串 2.0

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号