题目描述

给定一个长度为 \(n\) 的 01 串，你需要将它划分成若干段，每一段的长度都不超过 \(m\)，且满足以下两种条件之一：

1. 这个段中全部为 \(0\) 或全部为 \(1\).
2. 这个段中 \(0,1\) 数量之差不超过 \(k\).

你需要求出该 01 串合法的划分最少要多少段。

输入格式

第一行输入三个整数 \(n,m,k\)，分别表示 \(01\) 串的长度，段的长度限制，条件 \(1\) 中 \(0,1\) 数量差的限制。

接下来一行，输入一个长度为 \(n\) 的 \(01\) 串，表示该 \(01\) 串。

输出格式

一行，输出一个正整数，最少划分段数。

样例 #1

样例输入 #1

5 4 1
01110

样例输出 #1

2

样例 #2

样例输入 #2

20 5 1
10111101010011000100

样例输出 #2

6

提示

样例 1 解释：

一种符合条件的划分方式是 (01,110).

数据范围：

subtask	score	\(n\)	\(k\)	性质A
0	20	\(\le 2 \times 10^3\)	\(\le n\)	1
1	30	\(\le 2 \times 10^5 \)	\(\le n\)	0
2	20	\(\le 10^7\)	\(=0\)	0
3	30	\(\le 10^7\)	\(\le n\)	0

其中，性质 A 为：\(01\) 串随机生成，每一位均有一半的概率为 \(0\),一半的概率为 \(1\).\
表中性质 A 一栏为 \(1\) 则表示数据满足该性质。

对于 \(100\%\) 的数据，满足 \(n,m,k \le 10^7\)

下发文件

ssfz联测 下发文件