Zero-One (Hard Version) (Codeforces 1733D2)
Tags: Greedy, dp

This is the hard version of this problem. In this version, $$$n \le 5000$$$ holds, and this version has no restriction between $$$x$$$ and $$$y$$$. You can make hacks only if both versions of the problem are solved.You are given two binary strings $$$a$$$ and $$$b$$$, both of length $$$n$$$. You can do the following operation any number of times (possibly zero).   Select two indices $$$l$$$ and $$$r$$$ ($$$l < r$$$).  Change $$$a_l$$$ to $$$(1 - a_l)$$$, and $$$a_r$$$ to $$$(1 - a_r)$$$.  If $$$l + 1 = r$$$, the cost of the operation is $$$x$$$. Otherwise, the cost is $$$y$$$. You have to find the minimum cost needed to make $$$a$$$ equal to $$$b$$$ or say there is no way to do so.

Input: The first line contains one integer $$$t$$$ ($$$1 \le t \le 1000$$$) — the number of test cases.Each test case consists of three lines. The first line of each test case contains three integers $$$n$$$, $$$x$$$, and $$$y$$$ ($$$5 \le n \le 5000$$$, $$$1 \le x, y \le 10^9$$$) — the length of the strings, and the costs per operation.The second line of each test case contains the string $$$a$$$ of length $$$n$$$. The string only consists of digits $$$0$$$ and $$$1$$$.The third line of each test case contains the string $$$b$$$ of length $$$n$$$. The string only consists of digits $$$0$$$ and $$$1$$$.It is guaranteed that the sum of $$$n$$$ over all test cases doesn't exceed $$$5000$$$.

Output: For each test case, if there is no way to make $$$a$$$ equal to $$$b$$$, print $$$-1$$$. Otherwise, print the minimum cost needed to make $$$a$$$ equal to $$$b$$$.

Note: In the first test case, selecting indices $$$2$$$ and $$$3$$$ costs $$$8$$$, which is the minimum.In the second test case, we can perform the following operations.   Select indices $$$1$$$ and $$$2$$$. It costs $$$2$$$, and $$$a$$$ is 110001 now.  Select indices $$$2$$$ and $$$3$$$. It costs $$$2$$$, and $$$a$$$ is 101001 now.  Select indices $$$3$$$ and $$$4$$$. It costs $$$2$$$, and $$$a$$$ is 100101 now.  Select indices $$$4$$$ and $$$5$$$. It costs $$$2$$$, and $$$a$$$ is 100011 now.  Select indices $$$5$$$ and $$$6$$$. It costs $$$2$$$, and $$$a$$$ is 100000 now. The total cost is $$$10$$$.In the third test case, we cannot make $$$a$$$ equal to $$$b$$$ using any number of operations.In the fourth test case, we can perform the following operations.   Select indices $$$3$$$ and $$$6$$$. It costs $$$3$$$, and $$$a$$$ is 0101011 now.  Select indices $$$4$$$ and $$$6$$$. It costs $$$3$$$, and $$$a$$$ is 0100001 now. The total cost is $$$6$$$.In the fifth test case, we can perform the following operations.   Select indices $$$1$$$ and $$$6$$$. It costs $$$4$$$, and $$$a$$$ is 110000 now.  Select indices $$$2$$$ and $$$3$$$. It costs $$$3$$$, and $$$a$$$ is 101000 now. The total cost is $$$7$$$.In the sixth test case, we don't have to perform any operation.

Sample Inputs:
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

Sample Outputs:
8
10
-1
6
7
0

Solution (Python):
from re import A

def cal(l):
    if len(l) == 0:
        return 0
    if len(l) == 2:
        if l[1] - l[0] == 1:
            return min(x, 2 * y)
        else:
            return min(y, x * (l[1] - l[0]))
    if y <= x:
        return len(l) // 2 * y
    else:
        (a, b) = (0, 0)
        for i in range(len(l) - 1):
            d = a
            c = max(a, b + max(y - x * (l[i + 1] - l[i]), 0))
            (a, b) = (c, d)
        return len(l) // 2 * y - a
for _ in range(int(input())):
    (n, x, y) = map(int, input().split())
    a = input()
    b = input()
    l = []
    for i in range(n):
        if a[i] != b[i]:
            l.append(i)
    if len(l) % 2 == 0:
        print(cal(l))
    else:
        print(-1)

Solution (Python):
import sys
input = sys.stdin.readline

def solve():
    (n, x, y) = map(int, input().split())
    A = input().strip()
    B = input().strip()
    diff = []
    for i in range(n):
        if A[i] != B[i]:
            diff.append(i)
    m = len(diff)
    if x >= y:
        if m % 2:
            return -1
        elif m == 2:
            return y if diff[0] + 1 < diff[1] else min(2 * y, x)
        else:
            return y * (m // 2)
    elif m % 2:
        return -1
    elif m == 0:
        return 0
    else:
        dp = [[0, 0] for _ in range(m + 1)]
        dp[-1] = [0, float('inf')]
        dp[-2] = [float('inf'), y]
        for i in range(m - 2, -1, -1):
            dp[i][0] = min((diff[i + 1] - diff[i]) * x + dp[i + 2][0], dp[i + 1][1])
            dp[i][1] = min((diff[i + 1] - diff[i]) * x + dp[i + 2][1], y + dp[i + 1][0])
        return dp[0][0]
for _ in range(int(input())):
    print(solve())

Solution (Python):
import sys

def read(f):
    (n, x, y) = map(int, f.readline().split())
    a = f.readline().strip()
    b = f.readline().strip()
    zs = [i for (i, (c, d)) in enumerate(zip(a, b)) if c != d]
    return (zs, x, y)

def solve():
    (zs, x, y) = read(sys.stdin)
    if len(zs) % 2 != 0:
        print(-1)
        return
    if len(zs) == 0:
        print(0)
        return
    if x >= y:
        if len(zs) == 2 and zs[0] + 1 == zs[1]:
            print(min(x, 2 * y))
        else:
            print(len(zs) // 2 * y)
    else:
        f = []
        for (i, z) in enumerate(zs):
            if i == 0:
                cur = y
            elif i == 1:
                cur = min(2 * y, 2 * x * (z - zs[0]))
            else:
                cur = min(2 * x * (z - zs[i - 1]) + f[i - 2], y + f[i - 1])
            f.append(cur)
        print(f[-1] // 2)

def main():
    T = int(input().strip())
    for t in range(1, T + 1):
        solve()
if __name__ == '__main__':
    main()