描述:
喜多川同学今天正在参加 cosplay 展,现在准备拍合照!
对于一张合照,cosplayer 们会排成一行,如果对于任意至少有两个 cosplayer
的连续片段,男性的数量都不超过女性的数量,我们则称这张合影是美丽的。
现在已有 n 位 cosplayer 排成了一行,我们用一个二进制的字符串表示,其中
的 0 代表男性,1 代表女性。为了保证合影是美丽的,我们可以在任意位置邀请一
些额外的 cosplayer(可能为 0)。请注意您不能从队伍中移走任何 cosplayer。
现在喜多川同学想知道最少需要邀请几位 cosplayer 才能让合影是美丽的,怎么思考呢?
输入:
输入两行
第一行为一个正整数 n,表示初始状态下队伍中 cosplayer 的数量。
第二行为一个长度为 n 的二进制字符串,表示初始状态下队伍中 cosplayer 的
性别,其中 0 代表男性,1 代表女性。
输出:
输出一行。
表示最少需要邀请的 cosplayer 的数量。
按照题意,如果四个都是0,那至少需要3个1,如果5个都是0,那至少需要4个1,任意两个以上连续片段0不能能超过1,那要么是01,要么11,所以说最少的情况就是1个0搭配1个1,n-1就是最少需要1的数量,再减去已经有的1的数量,就是结果,