#500. 「新年欢乐赛 2019」我是念诗大王

内存限制:256 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: Wahacer

题目描述

题目背景

在上次的寒假速冻赛,Wahacer在众多dalao们的帮助下通过了鸽子联盟首长Ghoster的考验,他成功地指出了那些是真诗,那些是假诗,加入了鸽子联盟。但是与此同时,告诉Wahacer真相的雷神Misaka坐不住了,热爱念诗的Misaka不忍心看到Wahacer这样的念诗鬼才被Ghoster抢走。

于是Misaka私下会见了Ghoster,并念了一首“改革春风吹满地”打败了Ghoster。就这样,Wahacer又转入了Misaka麾下。但是Misaka仍然对Wahacer的念诗才能深感怀疑,于是趁着大过年,Misaka出了一道题来考考Wahacer。

题目描述

Misaka喜欢的诗句极具特色,他喜欢平仄相间的诗句,而且是前仄后平。如果这首诗不是平仄相间的话,Misaka就会强行把它改成平仄相间。我们用‘0’代表平,‘1’代表仄,用01串来代表一首诗句。例如一首诗是“0011”,Misaka就会用它所有的RP去将它改成“1010”,但是更改的规则必须是将一个‘1’与‘0’交换。而每交换一次,Misaka得RP就减少一点。于是Misaka就想用最少的RP来获得最多的“10(仄平)”。现在Misaka想要知道用至多K个RP可以最多得到几个“10”串?他把问题交给了Wahacer(因为这样减RP的就是Wahacer了),而身经百战的你可以帮助Wahacer解出谜题,过个好年吗?

输入格式

第一行输入 1 个数,为 RP 的数量 K

第二行是一个 01 串,表示诗句。

输出格式

一行数字,表示在使用了至多 K RP 改变原序列后最多能有几个“ 10 ”子串

样例

样例输入

2
00011

样例输出

2

样例说明

1 次交换位置 1 上的 0 和位置 4 上的 1 ,变为 10001

2 次交换位置 4 上的 0 和位置 5 上的 1 ,变为 10010

最后的串有 2 个“ 10 ”子串。

数据范围与提示

对于 10\% 的数据,有 01 串长度 N≤10

对于 30\% 的数据,有 K≤10

对于 40\% 的数据,有 01 串长度 N≤50

对于 100\% 的数据,有 01 串长度 N≤500,K≤100