修水表
该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。
题目描述
小 Z 同学喜欢查水表,这一天他来到了一条有 个排成一列的水表的街道查水表。
经过鉴定,他发现有一些水表损坏了。其中水表的情况用 串来表示, 表示水表没有损害, 表示水表损坏了。
- 例如, 表示从左往右分别表示没有损坏的水表、损坏的水表、没有损坏的水表、损坏的水表。
小 Z 每次可以修复一段长度为 的连续的水表( 覆盖的范围可以超出地图)。
小 Z 希望最多使用 次修复操作就可以将所有损坏的水表全部修复完成。他想知道能够达到这个目的的 最小值是多少。
输入格式
输入共两行。
第 行: 个整数,。
第 行: 个 串, 串长度为 N。
输出格式
输出共一行, 个整数,表示 的最小值。
输入输出样例
10 3
0101111011
3
5 1
11000
2
提示
【样例解释】
- 对于样例 , 的最小值为 ,即每次修复长度为 的连续水表,修复过程为 $0101111011 \rightarrow 0000111011 \rightarrow 00000000011 \rightarrow \rightarrow 0000000000$
- 对于样例 , 的最小值为 ,即每次修复长度为 的连续水表,修复过程为
【数据范围】
对于前 的数据,。
对于前 的数据,。
对于另外 的数据,保证 。
对于另外 的数据,保证 。
对于 的数据,。