这道题其实很考验思路喵~ 要用到动态规划才能优雅解决呢！经过猫猫的细心观察发现，如果把字符串中连续的 0 或 1 看作一个“大块”，那么华撃串恰好需要分成 4 个大块 喵！比如 000110111 可以分成 "000"、"11"、"0"、&
展开全文
看了一眼题解，都是dp做的，其实n<=500的话，直接枚举四个块的位置，然后讨论0101和1010两种情况也能过（具体每个块里面要操作多少次，可以通过前缀和求出这个块中原本1的个数 x ，如果这块最后要求全0则要操作x次，要求全1则要操作len-x次（len为块的长度）答案取所有情况的最小值即
展开全文
考虑到字符串长度很小，且需要的子串数目为 ，设计动态规划状态为 代表着进行到第 个字符时， 且目前要求子串数目等于 的最小代价，转移时 的增加与减小取决于枚举下一个字符与当前字符是否一致（ 大于 的状态直接舍弃）， 值的增加取决于枚举的字符相较于原串是否发生改变，时间复杂度为 。
#in
展开全文
n = int(input().strip())
s = input().strip() # 长度为 n 的 01 串
INF = 10**9
# dp[k][b]：处理到当前位置时，发生了 k 次相邻变化，且当前位置字符为 b(0/1) 的最少翻转次数
dp = [[INF] * 2 for
展开全文
"01" 和 "10" 子串的出现，在离散数学和字符串处理中等价于状态的跃迁（State Transition）。
当定义一个字符串中 count("01") + count("10") == 3 时，其核心几何与结构意
展开全文
提供一个简单的思路：
理解题意后可见最终状态是如下的其中一种
简而言之就是0块、1块交替，共4个块，两种情况分别考虑即可，此处行文以第一个情况为例。由于，可以接受直接枚举四个块的分界处。不妨将三个分界处记到前三个块的最后一个元素的索引。那么，对于第二个块，代价为
其中，指上0的个数，预处理即可
展开全文
-
扫描二维码，关注牛客
- 意见反馈
-
下载牛客APP，随时随地刷题
- 牛客竞赛，专业的竞技算法训练平台
-
扫描二维码，进入QQ群
扫码关注“比赛自动姬”
- 公司地址：北京市朝阳区北苑路北美国际商务中心K1座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备 11010502036488号
