← 返回题目列表

Codeforces · 1733/D2

D2. 零一(困难版)

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

这是这个问题的困难版本。在这个版本中,$$$n \le 5000$$$成立,并且这个版本在$$$x$$$和$$$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 1000$$$) — 测试用例的数量。

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

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

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

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

输出

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

示例

输入 #1

6
5 8 9
01001
00101
6 2 11
000001
100000
5 7 2
01000
11011
7 8 3
0111001
0100001
6 3 4
010001
101000
5 10 1
01100
01100

输出 #1

8
10
-1
6
7
0

注意

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

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

- 选择索引 $$$1$$$ 和 $$$2$$$。价格为 $$$2$$$,$$$a$$$ 现在是 110001。
- 选择索引 $$$2$$$ 和 $$$3$$$。花费 $$$2$$$,$$$a$$$ 现在是 101001。
- 选择索引 $$$3$$$ 和 $$$4$$$。它的价格是 $$$2$$$,$$$a$$$ 现在是 100101。
- 选择索引 $$$4$$$ 和 $$$5$$$。它的价格是 $$$2$$$,$$$a$$$ 现在是 100011。
- 选择索引 $$$5$$$ 和 $$$6$$$。花费$$$2$$$,$$$a$$$现在是100000。

总成本为 $$$10$$$。

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

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

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

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

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

- 选择索引 $$$1$$$ 和 $$$6$$$。价格是$$$4$$$,现在$$$a$$$是110000。
- 选择索引 $$$2$$$ 和 $$$3$$$。花费$$$3$$$,$$$a$$$现在是101000。

总成本为 $$$7$$$。

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