动态规划、字符串

设计 $dp_{i,j}$ 为将前 $i$ 个字符分成 $j$ 串时每个串包含的单词数量之和。

如果一个位置能匹配多个单词，无论匹配哪一个单词都只会消耗第一个字母，所以单词全部等效。预处理所有子串包含的单词数量即可。

使用 $n$ 表示字符串长度，$m$ 表示单词数量，$k$ 表示分割得到子串的数量，时间复杂度 $O(n^3m+n^2k)$。

注意处理非法的状态，比如 $dp_{1,2}$ 是非法的。

#include<bits/stdc++.h>
using namespace std;
ifstream fin("word.in");
ofstream fout("word.out");
int n,m,k,dp[205][45],w[205][205];
string s,c[10];
inline int word(int l,int r){
    string x=s.substr(l,r-l+1);
    int ret=0,pos=0,lim=r-l;
    while(pos<=lim){
        int nxt=lim+5;
        for(int i=1;i<=m;i++){
            int now=x.find(c[i],pos);
            if(~now) nxt=min(nxt,now);
        }
        if(nxt<=lim) ++ret;
        pos=nxt+1;
    }
    return ret;
}
int main(){
    fin>>n>>k,s='#';
    for(int i=1;i<=n;i++){
        string x;
        fin>>x,s+=x;
    }
    fin>>m,n*=20;
    for(int i=1;i<=m;i++) fin>>c[i];
    for(int l=1;l<=n;l++)
        for(int r=l;r<=n;r++) w[l][r]=word(l,r);
    memset(dp,128,sizeof(dp));
    dp[0][0]=0;
    for(int l=1;l<=n;l++)
        for(int r=l;r<=n;r++)
            for(int i=1;i<=k;i++) dp[r][i]=max(dp[r][i],dp[l-1][i-1]+w[l][r]);
    fout<<dp[n][k]<<'\n';
    return 0;
}