AlgoMooc
← 返回题库

P5904. 小红的 01 串

中等通过率 54% · 提交 13 · 通过 7
动态规划字符串贪心DP

小慕拿到了一个 ,他准备将若干个字符'1' 染成红色,将若干个字符'0' 染成蓝色,但有个限制:如果一个'0' 和一个'1' ,那么它们不能同时。 小慕想知道,最多可以染多少个字符?

提示:带虚线的词点一下有通俗解释。

输入描述

输入仅有一行,为小红拿到的 01 串。 字符串长度不超过200000。

输出描述

一个正整数,代表能染色的最多字符。

示例

示例 1

输入

110011

输出

4

时间限制 1000 ms · 内存限制 128 MB

看不懂题目?点开图解(训练营专属)

登录后查看题目图解

题目图解为训练营学员专属内容,请先登录。

微信扫码登录还不是训练营学员?了解训练营 →
写完代码点「提交」,将对全部测试用例判题。