T2-16 净化传输信号

题意理解

给定 source 字符串、pattern 字符串（保证是 source 的子序列）和可删除下标集合 targetIndices。求最多能删除多少个 targetIndices 中的字符，同时保证 pattern 仍是剩余字符串的子序列。

---

思路分析

转化问题： 最多能删除多少 = K - 最少需要保留多少

"最少需要保留多少"指：在 targetIndices 中，至少需要保留多少个字符才能保证 pattern 是子序列。

使用动态规划。

设 $dp[i][j]$ 表示：匹配 pattern 的前 $j$ 个字符，只考虑 source 的前 $i$ 个位置，最少需要保留多少个 targetIndices 中的字符。

状态转移：

1. 不用 source[i-1] 匹配：$dp[i][j] = dp[i-1][j]$
2. 用 source[i-1] 匹配 pattern[j-1]（需字符相同）：
   • 若 $i-1$ 在 targetIndices 中：$dp[i][j] = \min(dp[i][j], dp[i-1][j-1] + 1)$
   • 否则：$dp[i][j] = \min(dp[i][j], dp[i-1][j-1])$

边界条件：

• $dp[i][0] = 0$：匹配空 pattern 不需要保留任何字符
• $dp[0][j] = \infty$（$j > 0$）：空 source 无法匹配非空 pattern

答案： $K - dp[n][m]$

---

参考代码

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

const int MAXN = 3005;  // 最大字符串长度
const int INF = 0x3f3f3f3f;

char source[MAXN], pattern[MAXN];  // 原始串和模式串
int dp[MAXN][MAXN];    // dp[i][j]表示匹配pattern前j个字符最少需要保留多少targetIndices中的字符
bool inTarget[MAXN];   // inTarget[i]表示下标i是否在targetIndices中

int main() {
    cin >> source >> pattern;  // 读入原始串和模式串
    
    int n = strlen(source), m = strlen(pattern);  // 获取长度
    
    int K;  // 可删除下标数量
    cin >> K;
    
    for (int i = 0; i < K; i++) {  // 读入可删除下标
        int idx;
        cin >> idx;
        inTarget[idx] = true;  // 标记该下标在targetIndices中
    }
    
    for (int i = 0; i <= n; i++) {  // 初始化dp数组
        for (int j = 0; j <= m; j++) {
            dp[i][j] = (j == 0) ? 0 : INF;  // dp[i][0]=0，其他初始化为无穷大
        }
    }
    
    for (int i = 1; i <= n; i++) {  // 枚举source的前i个字符
        for (int j = 1; j <= m; j++) {  // 枚举pattern的前j个字符
            dp[i][j] = dp[i - 1][j];  // 不用source[i-1]匹配
            if (source[i - 1] == pattern[j - 1]) {  // 可以用source[i-1]匹配pattern[j-1]
                int cost = inTarget[i - 1] ? 1 : 0;  // 如果在targetIndices中，需要保留
                dp[i][j] = min(dp[i][j], dp[i - 1][j - 1] + cost);
            }
        }
    }
    
    cout << K - dp[n][m] << endl;  // 答案 = 总数 - 最少保留数
    return 0;
}