T2-5 字符串混合

题意理解

给定字符串 $A$、$B$、$C$，其中 $|C| = |A| + |B|$。$C$ 是由 $A$ 和 $B$ 交织而成但被修改过的，求最少修改 $C$ 中多少个字符才能让 $C$ 变成 $A$ 和 $B$ 的合法交织。

---

思路分析

使用动态规划。

设 $dp[i][j]$ 表示：用 $A$ 的前 $i$ 个字符和 $B$ 的前 $j$ 个字符，交织成 $C$ 的前 $i+j$ 个字符，最少需要修改的字符数。

状态转移：

$C[i+j-1]$ 要么来自 $A[i-1]$，要么来自 $B[j-1]$，取最小值：

$$dp[i][j] = min(dp[i-1][j] + cost_A, dp[i][j-1] + cost_B)$$

其中：

• $cost_A = (A[i-1] \neq C[i+j-1])$ ? $1$ : $0$
• $cost_B = (B[j-1] \neq C[i+j-1])$ ? $1$ : $0$

边界条件：

• $dp[0][0] = 0$
• $dp[i][0]$：只用 $A$ 的前 $i$ 个字符匹配 $C$ 的前 $i$ 个
• $dp[0][j]$：只用 $B$ 的前 $j$ 个字符匹配 $C$ 的前 $j$ 个

答案： $dp[|A|][|B|]$

---

参考代码

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 1005;  // 最大字符串长度

char A[MAXN], B[MAXN], C[MAXN * 2];  // 三个字符串
int dp[MAXN][MAXN];  // dp[i][j]表示A前i个和B前j个交织成C前i+j个的最少修改次数

int main() {
    int T;  // 测试数据组数
    cin >> T;
    
    while (T--) {  // 处理每组数据
        cin >> A >> B >> C;  // 读入三个字符串
        
        int lenA = strlen(A), lenB = strlen(B);  // 获取A和B的长度
        
        dp[0][0] = 0;  // 边界：空串匹配空串，不需要修改
        
        for (int i = 1; i <= lenA; i++) {  // 边界：只用A匹配C
            dp[i][0] = dp[i - 1][0] + (A[i - 1] != C[i - 1]);
        }
        
        for (int j = 1; j <= lenB; j++) {  // 边界：只用B匹配C
            dp[0][j] = dp[0][j - 1] + (B[j - 1] != C[j - 1]);
        }
        
        for (int i = 1; i <= lenA; i++) {  // 枚举A的前i个字符
            for (int j = 1; j <= lenB; j++) {  // 枚举B的前j个字符
                int pos = i + j - 1;  // C中当前位置的下标
                int costA = (A[i - 1] != C[pos]);  // 若C[pos]来自A[i-1]的修改代价
                int costB = (B[j - 1] != C[pos]);  // 若C[pos]来自B[j-1]的修改代价
                dp[i][j] = min(dp[i - 1][j] + costA, dp[i][j - 1] + costB);  // 取最小值
            }
        }
        
        cout << dp[lenA][lenB] << endl;  // 输出答案
    }
    
    return 0;
}