CF1415C Bouncing Ball

你正在为一款手机游戏设计一个关卡。该关卡包含若干个从左到右排列的格子，这些格子从 $1$ 开始按顺序编号。每个格子中你可以放置一个平台，也可以留空。 为了通过这个关卡，玩家必须从最左侧扔出一个球，使其首先落在第 $p$ 个格子的一个平台上，然后弹跳到第 $(p + k)$ 个格子的一个平台上，再弹跳到第 $(p + 2k)$ 个格子的一个平台上，依此类推，每次跳跃 $k$ 个格子，直到球跳出最后一个格子。如果这些格子中有任何一个没有平台，那么对于当前的 $p$ 和 $k$，该关卡就无法通过。 你已经有了一个初始的关卡布局 $a_1, a_2, a_3, \ldots, a_n$，其中 $a_i = 0$ 表示第 $i$ 个格子没有平台，$a_i = 1$ 表示有平台。你希望对其进行修改，使得该关卡可以通过给定的 $p$ 和 $k$。你可以进行以下两种操作： - 用 $x$ 秒在某个空格子中添加一个平台。 - 用 $y$ 秒完全移除第一个格子，格子的总数减少一，剩余格子的顺序保持不变并重新编号。 你不能进行其他操作。你不能将格子的总数减少到小于 $p$。  上图为第三个样例的说明。叉号表示被删除的格子，蓝色平台为新添加的平台。 请问，最少需要多少秒才能使该关卡可以通过给定的 $p$ 和 $k$？

第一行包含测试用例数 $t$（$1 \le t \le 100$）。接下来是每个测试用例的描述。 每个测试用例的第一行包含三个整数 $n$、$p$ 和 $k$（$1 \le p \le n \le 10^5$，$1 \le k \le n$），分别表示格子的数量、首个需要有平台的格子编号以及球弹跳的周期。 第二行包含一个长度为 $n$ 的字符串 $a_1 a_2 a_3 \ldots a_n$（$a_i = 0$ 或 $a_i = 1$），表示初始的关卡布局，字符串中没有空格。 最后一行包含两个整数 $x$ 和 $y$（$1 \le x, y \le 10^4$），分别表示添加一个平台和移除第一个格子所需的时间。 所有测试用例中 $n$ 的总和不超过 $10^5$。

对于每个测试用例，输出一个整数，表示最少需要多少秒才能按要求修改关卡。 可以证明，总是存在一种方法使关卡可以通过。

在第一个样例中，最优做法是直接移除第一个格子，此后所有需要的平台都已就位：0101010101。被删除的数字用删除线表示，加粗的数字表示需要有平台的位置。所需时间为 $y = 2$。 在第二个样例中，最优做法是在第 $4$ 和第 $5$ 个格子各添加一个平台：00000 $\to$ 00011。所需时间为 $x \cdot 2 = 4$。 在第三个样例中，最优做法是先移除第一个格子两次，然后在最初的第 $10$ 个格子的位置添加一个平台：10110011000 $\to$ 10110011010。所需时间为 $y \cdot 2 + x = 10$。 由 ChatGPT 4.1 翻译