CF1346B Boot Camp

伯兰国立大学（BSU）正在举办一场编程训练营。训练营将持续 $n$ 天，BSU 的讲师们计划在这些天内安排若干场讲座。 训练营中的某些天已经被安排为游览日，这些天不能安排讲座。为了防止参与者因学习编程而过度疲劳，每天的讲座数量不得超过 $k_1$，并且任意连续两天的讲座总数不得超过 $k_2$。 你能计算出在训练营期间最多可以安排多少场讲座吗？形式化地说，找到最大的整数 $m$，使得可以选择 $n$ 个非负整数 $c_1, c_2, \dots, c_n$（其中 $c_i$ 表示第 $i$ 天安排的讲座数量），满足以下条件： - $c_1 + c_2 + \dots + c_n = m$； - 对于每个游览日 $d$，有 $c_d = 0$； - 对于每一天 $i$，有 $c_i \leq k_1$； - 对于每一对连续的天数 $(i, i+1)$，有 $c_i + c_{i+1} \leq k_2$。 注意，某些非游览日也可以不安排讲座（即即使 $i$ 不是游览日，也可能有 $c_i = 0$）。

第一行包含一个整数 $t$（$1 \leq t \leq 50$），表示测试用例的数量。 接下来是 $t$ 组测试数据，每组测试数据包含两行。第一行包含三个整数 $n$、$k_1$、$k_2$（$1 \leq n \leq 5000$；$1 \leq k_1 \leq k_2 \leq 200\,000$）。 第二行包含一个长度为 $n$ 的字符串 $s$，仅由字符 $0$ 或 $1$ 组成。如果 $s_i = 0$，则第 $i$ 天为游览日（这一天不能安排讲座）；如果 $s_i = 1$，则第 $i$ 天不是游览日。

对于每组测试数据，输出一个整数，表示最多可以安排的讲座总数 $m$。

由 ChatGPT 4.1 翻译