给定一个长度为n的01串，定义“连续段"为极长注续的相同字符的数量，例如001110000'有一个长度为2的0连续段，长度为3的1连续段，长度为4的0的连续段。 已知每次操作可以把一个0变成1或者把1变成0。 现在请你用最少的操作欢数，使得所有0连续段的长度都是a的倍数，1连续段的长度都是b的倍数。 输入描述：第一行输人三个正整数n， a, b 第二行输入一个长度为n的，仅有字符0和1构成的字符串，其中1<= n, a, b,<=20000. 输出描述：使得字符串合法的最小操作次数，特殊的，如果无论如何字符串都不能合法，输出-1. 示例：输入 8 2 3 10111000 输出：2

思路：动态规划

设 $dp_{i, j}$ 表示前 $i$ 个字符，0 连续段长度为 $j \times a$，且最后一个连续段是 0 的最小操作次数。类似地，设 $dp_{i, j, 1}$ 表示前 $i$ 个字符，1 连续段长度为 $j \times b$，且最后一个连续段是 1 的最小操作次数。

考虑转移，假设现在枚举到第 $i$ 个字符，如果第 $i$ 个字符是 0，那么有两种情况：

- 将其接到前面的 0 连续段中去，此时操作数不变，故 $dp_{i, j} = dp_{i-1, j}$。
- 将其作为新的一段 0 连续段的结尾，此时需要将前面所有的数都变成 1，操作数为 $\sum_{k=i-j \times a+1}^{i-1} (s_k == 1)$，其中 $s_k$ 表示第 $k$ 个字符，表示 $j \times a$ 个 0 的长度为 $j \times a$。

因此转移方程为：

$$ dp_{i,j}=\min\{dp_{i-1,j},\sum_{k=i-j \times a+1}^{i-1} (s_k == 1) + dp_{i-j \times a, j-1, 1}\} $$

其中 $dp_{i-j \times a, j-1, 1}$ 表示所有 1 连续段以 $j \times b$ 为长度的连续段结尾所需的最小操作数。

如果第 $i$ 个字符是 1，同理可得：

$$ dp_{i,j,1}=\min\{dp_{i-1,j,1},\sum_{k=i-j \times b+1}^{i-1} (s_k == 0) + dp_{i-j \times b, j-1}\} $$

细节处理：

- 当 $j$ 不能整除 $a$ 或 $b$ 的时候，那么不存在合法的方案，输出 -1。
- 初始化 $dp_{i, 0} = dp_{i, 0, 1} = 0$，表示连续段长度为 0 的时候，不需要操作。

最终，答案为 $dp_{n, a}$。若无法达成合法方案，输出 -1。

时间复杂度为 $\mathcal{O}(n \times \max\{a, b\})$。

参考代码：