LuoguP2875

· · 题解

分析：

首先在读 题 完毕后，发现暴力的做法也不是很好做，再回想关于字符串的种种问题，发现没有什么字符串的模型可以使用，尽管模仿 电子字典 似乎可行，但仔细一想，对蓝题这么做是在没有必要，并且确实想不出一个可行的方案前进，所以向 dp 方面想。

具体方案：

既然有这个方向，就继续思考，设一个简单的状态，f_i 就指话说到 i 时，最少删去的字母个数，然后就可以想状态转移了。

显而易见的，如果枚举到 i 时，我们不选这一个字母，即删掉这个字母，就简单的转移为 f_i = f_{i-1} + 1，难点在于如果考虑不删这个字母，应该怎么转移。

我们思考一下，如果不删这个字母，肯定是因为加上了它，可以与前面的某些字母组成一个单词，比如 \texttt{abcd}，我们加入一个 e，同时有一个单词 \texttt{bde}，那么转移时就是 f_5 = f_{5 - 4} + 1，其中 5 代表枚举到第 5 个；4 表示我们选了一个长度为 3 的单词，而且扔掉了 1 个字母，所以是 3 + 1；1 表示我们在选那个单词时扔掉了 1 个字母。

所以策略就自然而然跳了出来，我们可以枚举每一个单词，看看以选的这个字母为结尾时，需要多少个字母才能组出来（比如上面的例子，字母是 \texttt{e}，单词是 \texttt{bde}，那么需要 \texttt{bcde} 这 4 个字母才能组成，其中就包括一个被扔掉的），并在过程中判断这个单词是否可选。设 le_j 为选了第 j 个单词后需要把指针指在哪里（比如上面的例子，指针指在了 a 后面的 b），sum 表示中间扔掉了多少字母，状态转移为

f_i=\min\{f_i,f_{le-1}+sum\}

接下来看如何求 le 和 sum，可以同时设两个变量 i 和 j，分别是母串中枚举到的地方和我们枚举尝试的单词的末尾，设母串是 s，单词是 c，每次比较 s_i 和 c_j，若相等，就 j \leftarrow j+1，否则，sum \leftarrow sum +1，并且无论如何都使 i \leftarrow i+1，这样，最后 i 的位置就是 le。

代码如下，仅供参考（代码中单词是 s，母串是 c）：

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n, l, f[305], len[605];
char c[305];
string s[605];
int aaa(int x, int y, int &le){
    int j = len[y], sum = 0;
    le = -1;
    for(int i = x; i >= 1; i --){
        if(c[i] == s[y][j])
        j --;
        else
        sum ++;
        if(j == 0){
            le = i;
            break;
        }
    }
    return sum;
}
signed main(){
    scanf("%lld%lld%s", &n, &l, c + 1);
    for(int i = 1; i <= n; i ++){
        cin >> s[i];
        len[i] = s[i].size();
        s[i] = "0" + s[i];
    }
    f[0] = 0;
    for(int i = 1; i <= l; i ++){
        f[i] = f[i - 1] + 1;
        for(int j = 1; j <= n; j ++){
            int le;
            int sum = aaa(i, j, le);
            if(le != -1)
            f[i] = min(f[i], f[le - 1] + sum);
        }
    }
    printf("%lld", f[l]);
    return 0;
}

祝各位大佬刷题愉快。