题解：P2432 zxbsmk爱查错

外婆的信件修正问题

这是一个典型的动态规划问题，我们需要从给定的字符串中删除尽可能少的字符，使得剩余的字符能够组成一个或多个合法的单词。

方法思路

问题分析：

我们需要从字符串中删除最少的字符，使得剩余的字符可以被分割成若干个合法的单词。

每个单词必须按顺序出现在字符串中，但可以不连续。

动态规划设计：

定义状态：dp[ $i$ ] 表示处理到字符串的第  $i$  个字符时，最少需要删除的字符数。

状态转移：对于每个位置  $i$ ，我们考虑所有可能的单词  $w$ ，如果  $w$  可以从位置  $j$  开始匹配到位置 $ i$ ，则更新 dp[ $i$ ] 的值。

预处理单词匹配：

对于每个单词  $ $ $w$ $ $  和每个可能的起始位置  $ $ $j$ $ $ ，预处理出该单词能够匹配到的最远位置 k，以及删除的字符数。

```cpp
#include <iostream>
#include <vector>
#include <string>
#include <climits>
#include <algorithm>
using namespace std;

struct Match {
    int end_pos;
    int deletions;
};

int main() {
    int W, L;
    cin >> W >> L;
    
    string s;
    cin >> s;
    
    vector<string> words(W);
    for (int i = 0; i < W; ++i) {
        cin >> words[i];
    }
    
    // 预处理每个单词在每个起始位置j的匹配情况
    vector<vector<Match>> match_info(W);
    for (int w_idx = 0; w_idx < W; ++w_idx) {
        const string& w = words[w_idx];
        int m = w.length();
        match_info[w_idx].resize(L);
        
        for (int j = 0; j < L; ++j) {
            int k = j;
            int matched = 0;
            int deletions = 0;
            
            while (k < L && matched < m) {
                if (s[k] == w[matched]) {
                    ++matched;
                } else {
                    ++deletions;
                }
                ++k;
            }
            
            if (matched == m) {
                match_info[w_idx][j] = {k - 1, deletions};
            } else {
                match_info[w_idx][j] = {-1, -1}; // 无效匹配
            }
        }
    }
    
    // 动态规划初始化
    vector<int> dp(L + 1, INT_MAX);
    dp[0] = 0; // 处理到第0个字符时，删除0个字符
    
    for (int i = 1; i <= L; ++i) {
        // 情况1：删除当前字符
        if (dp[i - 1] != INT_MAX) {
            dp[i] = dp[i - 1] + 1;
        }
        
        // 情况2：当前字符是某个单词的结尾
        for (int w_idx = 0; w_idx < W; ++w_idx) {
            const string& w = words[w_idx];
            int m = w.length();
            if (m > i) continue;
            
            int j = i - m; // 单词的起始位置可能是j
            // 检查所有可能的起始位置j' <= j
            for (int j_prime = 0; j_prime <= j; ++j_prime) {
                const Match& match = match_info[w_idx][j_prime];
                if (match.end_pos == i - 1) { // 匹配到i-1位置
                    if (dp[j_prime] != INT_MAX) {
                        dp[i] = min(dp[i], dp[j_prime] + match.deletions);
                    }
                }
            }
        }
    }
    
    cout << dp[L] << endl;
    
    return 0;
}    
```

代码解释

预处理匹配信息：

对于每个单词  $ $w$ $  和每个可能的起始位置  $ $j$ $ ，计算该单词能够匹配到的最远位置  $ $k$ $  和删除的字符数。

存储这些信息在 match_info 数组中，以便后续快速查询。

动态规划初始化与状态转移：

dp[ $ $i$ $ ]  表示处理到第  $ $i$ $  个字符时所需的最少删除次数。

对于每个位置  $ $i$ $ ，考虑两种情况：

删除当前字符，继承前一位置的删除次数并加 1。

当前字符是某个单词的结尾，检查所有可能的单词和起始位置，更新删除次数。

结果输出：

最终 dp[ $L$ ] 即为处理完整个字符串所需的最少删除次数。

正在渲染内容...