Boot Camp

题意翻译

- BSU 将要举办一次编程训练营，训练营将持续 $n$ 天，BSU 的讲师计划在这期间举办一些讲座。 - $n$ 天中有若干天为游玩日，游玩日不应举办任何讲座。同时为了学员不会厌倦，每天的讲座次数不应超过 $k_1$，每两天的总讲座次数不应超过 $k_2$。 - 需要你计算 $n$ 天中最多举办多少次讲座。形式化地，求出最大整数 $m$,使得可以找出 $n$ 个数 $c_1,c_2,\dots c_n$(其中 $c_i$ 表示第 $i$ 天讲座的数量)，满足： * $\sum\limits_{i=1}^{n}c_i=m$； * 对于每个游玩日 $d$ ，$c_d=0$； * 对于第 $i$ 天，$c_i\le k_1$； * 对于第 $i$ 天和第 $i+1$ 天,$c_i+c_{i+1}\le k_2$； 需要注意的是，即使某一天不是游玩日，这一天的讲座数量也可能为 0。 * 输入有 $t$ 组数据，每组数据的第一行为三个整数 $n,k_1,k_2$,第二行为一个01串，如果01串的第 $i$ 位为 0，则代表第 $i$ 天为出游日。对于每组数据，输出一行一个数 $m$ 代表你得出的答案。 * **本题提交语言限制为 Kotlin,提交其他语言评测结果为 Waiting**

题目描述

Berland State University (BSU) is conducting a programming boot camp. The boot camp will last for $ n $ days, and the BSU lecturers are planning to give some number of lectures during these days. Some days of the boot camp are already planned as excursion days, and no lectures should be held during these days. To make sure the participants don't get too tired of learning to program, the number of lectures for each day should not exceed $ k_1 $ , and the number of lectures for each pair of consecutive days should not exceed $ k_2 $ . Can you calculate the maximum number of lectures that can be conducted during the boot camp? Formally, find the maximum integer $ m $ such that it is possible to choose $ n $ non-negative integers $ c_1 $ , $ c_2 $ , ..., $ c_n $ (where $ c_i $ is the number of lectures held during day $ i $ ) so that: - $ c_1 + c_2 + \dots + c_n = m $ ; - for each excursion day $ d $ , $ c_d = 0 $ ; - for each day $ i $ , $ c_i \le k_1 $ ; - for each pair of consecutive days $ (i, i + 1) $ , $ c_i + c_{i + 1} \le k_2 $ . Note that there might be some non-excursion days without lectures (i. e., it is possible that $ c_i = 0 $ even if $ i $ is not an excursion day).

输入输出格式

输入格式

The first line contains one integer $ t $ ( $ 1 \le t \le 50 $ ) — the number of testcases. Then the testcases follow, each consists of two lines. The first line contains three integers $ n $ , $ k_1 $ , $ k_2 $ ( $ 1 \le n \le 5000 $ ; $ 1 \le k_1 \le k_2 \le 200\,000 $ ). The second line contains one string $ s $ consisting of exactly $ n $ characters, each character is either 0 or 1. If $ s_i = 0 $ , then day $ i $ is an excursion day (so there should be no lectures during that day); if $ s_i = 1 $ , then day $ i $ is not an excursion day.

输出格式

For each test case, print one integer — the maximum possible value of $ m $ (the number of lectures that can be conducted).

输入输出样例

输入样例 #1

4
4 5 7
1011
4 4 10
0101
5 3 4
11011
6 4 6
011101

输出样例 #1

12
8
8
14