← 返回题目列表

Codeforces · 1346/B

B. 训练营

中文机器翻译题面 查看原题

Berland 州立大学 (BSU) 正在举办编程训练营。训练营将持续 $$$n$$$ 天,BSU 讲师计划在这些天里进行一些讲座。

新兵训练营的某些日子已计划为游览日,这些天不应举办任何讲座。为了确保参与者不会对学习编程感到太厌倦,每天的讲座次数不应超过$$$k_1$$$,并且每对连续天的讲座次数不应超过$$$k_2$$$。

你能计算一下训练营期间最多可以进行多少次讲座吗?形式上,找到最大整数$$$m$$$,以便可以选择$$$n$$$非负整数$$$c_1$$$、$$$c_2$$$、...、$$$c_n$$$(其中$$$c_i$$$是$$$i$$$当天举办的讲座数量),以便:

- $$$c_1 + c_2 + \dots + c_n = m$$$;
- 每个游览日 $$$d$$$, $$$c_d = 0$$$;
- 每天 $$$i$$$, $$$c_i \le k_1$$$;
- 对于每对连续天 $$$(i, i + 1)$$$, $$$c_i + c_{i + 1} \le k_2$$$。

请注意,可能有一些非游览日没有讲座(即,即使 $$$i$$$ 不是游览日,$$$c_i = 0$$$ 也可能是这样)。

输入

第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 50$$$) — 测试用例的数量。

然后是测试用例,每个测试用例由两行组成。第一行包含三个整数 $$$n$$$、$$$k_1$$$、$$$k_2$$$ ($$$1 \le n \le 5000$$$; $$$1 \le k_1 \le k_2 \le 200\,000$$$)。

第二行包含一个字符串$$$s$$$,恰好由$$$n$$$个字符组成,每个字符要么是0,要么是1。如果$$$s_i = 0$$$,则$$$i$$$日是游览日(因此当天应该没有讲座);如果 $$$s_i = 1$$$,则 $$$i$$$ 日不是游览日。

输出

对于每个测试用例,打印一个整数 - $$$m$$$ 的最大可能值(可以进行的讲座数量)。

示例

输入 #1

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

输出 #1

12
8
8
14