string - 将字符串转换为其他字符串的最低成本

Question

给定 2 个长度为 N 的字符串 A 和 B。A 包含 '0'、'1' 和 '?'； B 仅包含“0”和“1”。我们需要通过对字符串 A 执行一系列允许的操作来找到将 A 转换为 B 的最小成本。

允许以下操作:

1. 用成本 x 将“0”更改为“1”
2. 将'1'更改为'0'，费用为y
3. 改变'?'成本为 z 的“0”或“1”
4. 交换两个相邻的字符，代价为t。

我们需要找到最低成本。

示例:令 N=6 , x=1 , y=1000 , z=1 , t=1 , A=01??00 和 B=001010 则答案为 4。

如何使用动态规划解决这个问题？有什么可以复发的呢？请帮忙

Answer 1

让我们从一些观察开始:

1. 如果我们匹配两个字符串中的所有 1，则会自动匹配 0。

2. 操作顺序无关紧要。也就是说，我们可以假设我们首先进行所有更改(0 到 1、1 到 0 或 ? 到某物)，然后我们执行所有交换。

3. 假设 1 在第一个字符串 a (p_1, p_2, ..., p_n) 中的位置是 (q_1, q_2 , ..., q_n)。然后，如果我们按排序顺序将 p 与 q 匹配，我们将交换成本降至最低。

4. 让我们看一下位置 i 和 i + 1。让我们将 balance[i] 定义为长度 i + 1< 前缀中 a 和 b 中的个数之差。那么恰好 balance[i] 交换将触及这两个元素。第 3 步隐含了此声明。

5. 所有这些观察导致以下动态规划解决方案:状态是(prefix length, current balance)。该值是处理给定长度的前缀以使余额等于指定值的最小成本。有 O(N ^ 2) 个状态。如何进行过渡？我们可以尝试将所有内容都放在 a 的当前位置并适本地计算成本。

6. 答案是f(N, 0)。

这是一些代码:

public class Task {

    final int INF = 1_000_000_000;

    int cost01;
    int cost10;
    int costUnknown;
    int costSwap;

    int getDeltaBalance(int c1, int c2) {
        return c1 - c2;
    }

    int getCost(char start, int want) {
        if (start == '?')
            return costUnknown;
        if (start - '0' == want)
            return 0;
        if (start == '1')
            return cost10;
        return cost01;
    }

    public void solve(Scanner in, PrintWriter out) throws IOException {
        int n = in.nextInt();
        cost01 = in.nextInt();
        cost10 = in.nextInt();
        costUnknown = in.nextInt();
        costSwap = in.nextInt();
        String a = in.next();
        String b = in.next();
        int[][] dp = new int[n + 1][2 * n + 1];
        for (int i = 0; i <= n; i++) {
            Arrays.fill(dp[i], INF);
        }
        dp[0][n] = 0;
        for (int pos = 0; pos < n; pos++) {
            for (int balance = -n; balance <= n; balance++) {
                for (int curNumber = 0; curNumber <= 1; curNumber++) {
                    int newBalance = balance + getDeltaBalance(curNumber, b.charAt(pos) - '0');
                    if (newBalance < -n || newBalance > n)
                        continue;
                    int newCost = dp[pos][balance + n] + costSwap * Math.abs(balance)
                            + getCost(a.charAt(pos), curNumber);
                    dp[pos + 1][newBalance + n] = Math.min(dp[pos + 1][newBalance + n], newCost);
                }
            }
        }
        out.println(dp[n][n]);
    }
}