← 返回题目列表

Codeforces · 1733/D1

D1. 零一(简易版)

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

这是问题的简单版本。在此版本中,$$$n \le 3000$$$、$$$x \ge y$$$ 成立。只有当问题的两个版本都得到解决时,你才能进行黑客攻击。

给定两个二进制字符串 $$$a$$$ 和 $$$b$$$,长度均为 $$$n$$$。您可以执行以下操作任意次数(可能为零)。

- 选择两个索引 $$$l$$$ 和 $$$r$$$ ($$$l < r$$$)。
- 将 $$$a_l$$$ 更改为 $$$(1 - a_l)$$$,将 $$$a_r$$$ 更改为 $$$(1 - a_r)$$$。
- 如果 $$$l + 1 = r$$$,则操作成本为 $$$x$$$。否则,成本为$$$y$$$。

你必须找到使 $$$a$$$ 等于 $$$b$$$ 所需的最低成本,或者说没有办法这样做。

输入

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

每个测试用例由三行组成。每个测试用例的第一行包含三个整数 $$$n$$$、$$$x$$$ 和 $$$y$$$($$$5 \le n \le 3000$$$、$$$1 \le y \le x \le 10^9$$$)— 字符串的长度以及每次操作的成本。

每个测试用例的第二行包含长度为 $$$n$$$ 的字符串 $$$a$$$。该字符串仅由数字 $$$0$$$ 和 $$$1$$$ 组成。

每个测试用例的第三行包含长度为 $$$n$$$ 的字符串 $$$b$$$。该字符串仅由数字 $$$0$$$ 和 $$$1$$$ 组成。

保证所有测试用例的 $$$n$$$ 总和不超过 $$$3000$$$。

输出

对于每个测试用例,如果无法使 $$$a$$$ 等于 $$$b$$$,则打印 $$$-1$$$。否则,打印使 $$$a$$$ 等于 $$$b$$$ 所需的最小成本。

示例

输入 #1

4
5 8 7
01001
00101
5 7 2
01000
11011
7 8 3
0111001
0100001
5 10 1
01100
01100

输出 #1

8
-1
6
0

注意

在第一个测试用例中,选择索引 $$$2$$$ 和 $$$3$$$ 的成本为 $$$8$$$,这是可能的最小成本。

在第二个测试用例中,我们无法使用任意数量的操作使 $$$a$$$ 等于 $$$b$$$。

在第三个测试用例中,我们可以执行以下操作:

- 选择索引 $$$3$$$ 和 $$$6$$$。它的价格为 $$$3$$$,$$$a$$$ 现在是 0101011。
- 选择索引 $$$4$$$ 和 $$$6$$$。花费 $$$3$$$,$$$a$$$ 现在是 0100001。

总成本为 $$$6$$$。

在第四个测试用例中,我们不必执行任何操作。