思路:动态规划 + 前缀最值优化

Step1:朴素dp

考虑动态规划，做过Leetcode-132 或者 CodeFun2000-P1168 这种题的话，就会很自然的想到一个$O(n^2)$的朴素$dp$:

状态：

$dp_{i,j \in \{0,1\}}$ 代表考虑了字符串的前$i$个位置并且最后一段是$j$ 的最小修改次数。

感谢群友XXX的真题投稿

题目内容

塔子哥是一名信息学竞赛的热爱者，他从小就对编程和算法有着浓厚的兴趣。他经常参加各种信息学竞赛，从NOIP到NOI，再到IOI，他都有着不俗的成绩。他的梦想是成为一名优秀的程序员，为人类社会贡献自己的智慧。

有一天，塔子哥收到了一个来自国际信息学奥林匹克竞赛（IOI）组委会的邀请函，邀请他参加一个特别的挑战。这个挑战是由一位神秘的信息学大师设计的，只有通过了这个挑战，才能得到大师的认可和指导。塔子哥对此感到非常兴奋，他立刻打开了邀请函中附带的链接，进入了一个在线评测系统。

在评测系统中，塔子哥看到了这样一个题面：

给定一个长度为 $n$ 的 01 串，你需要将其中的一些数字进行修改，使得所有连续的 0 的长度都是 $a$ 的倍数，而所有连续的 1 的长度都是 $b$ 的倍数。

为了解决这个问题，你可以对串中的某些位置进行修改，将 0 变为 1 或者将 1 变为 0 。但是你希望尽可能地少进行修改操作。

现在，请你告诉我你最少需要进行多少次操作才能达到上述要求。

输入描述

第一行输入三个正整数 $n$ ， $a$ ， $b$ 。

第二行输入一个长度为 $n$ 的仅包含字符 0 和 1 的字符串。

$1\le n,a,b \le 200000$

输出描述

使得字符串合法的最小操作次数，特别的，如果无论如何字符串都不能合法，请输出 $-1$ 。

样例1

输入

5 2 1
01011

输出

2

样例2

输入

8 4 2
01010001

输出

3

样例3

输入

8 3 3
01010001

输出

-1