closefrom

所用函数（string s,a;）：

s.substr(x,len) 在s中取出从x位置开始，长度为len的字符串，并返回string类型的字符串。

s.find(a) 在s中查找字符串a,并返回起始下标（从0开始），若不存在，返回1844674407370955161，即（1999999999999999）16.

s.length() 求s的长度（从0开始）。

s[1] 字符串s的第2个字符，相当于数组（后来因为有了substr，就不用了）。

然后是DP：dp[i][j]表示到了第i个位置，分了j块，能得到的最多的单词数。

转移：枚举断点l，则 dp[i][j]=max{ dp[i][j] , dp[l][j-1]+sum[l+1][i] };

sum[i][j] 是预处理的表示从i到j的单词数。

#include <cstdio>
#include <cstring>
#include <string>
#include <iostream>
using namespace std;
int p,k,s,sum[205][205],dp[205][45],plen;
string sa[10],pstr,xstr;
int max(int a,int b){return a>b?a:b;}
bool can(int a,int b){
    string ssr=pstr.substr(a,b-a+1);
    for(int i=1;i<=s;i++)if(ssr.find(sa[i])==0)return true;
    return false;
}
int main(){
    pstr+='0';
    scanf("%d%d",&p,&k);
    //printf("%d %d ",p,k);
    //scanf("%s",xstr);printf("%s ",xstr);
    for(int i=1;i<=p;i++){cin >> xstr;pstr+=xstr;}
    scanf("%d",&s);
    //printf("%d  ",s);
    for(int i=1;i<=s;i++)cin >> sa[i];
    plen=pstr.length()-1;
    for(int i=plen;i>=1;i--){
        for(int j=i;j>=1;j--){
            sum[j][i]=sum[j+1][i];
            if(can(j,i))sum[j][i]++;
        }
    }
/*
因为从后往前推，所以是+ =>sum[j][i]=sum[j+1][i];
即，j到i位置匹配的单词数，一定等于j+1到i位置匹配的单词数，
然后can函数检查是否还能再匹配一个
*/
    for(int i=1;i<=k;i++)dp[i][i]=dp[i-1][i-1]+sum[i][i];
    for(int i=1;i<=plen;i++)dp[i][1]=sum[1][i];
/*
处理特殊情况，前i个位置的数分成i块，也就是一个数为一块，
状态为dp[i-1][i-1]+sum[i][i],
表示前i-1个数分成i-1块的单词数加上当前i位置到i位置的单词数

还有一种情况就是前i个数分成一块，也就是前i个数的单词数 即=>dp[i][1]=sum[1][i];
*/
    //test
    //for(int i=1;i<=plen;i++){for(int j=1;j<=plen;j++){printf("%d ",sum[i][j]);}printf("\n");}
    
    for(int i=1;i<=plen;i++)
        for(int j=1;j<=k&&j<i;j++)
            for(int l=j;l<i;l++)
                dp[i][j]=max(dp[i][j],dp[l][j-1]+sum[l+1][i]); 
/*
第一个循环表示为前i个数
第二个循环表示为可以分成1-i块, 且 小于等于k
第三个循环表示为将前i个数，分成两部分，范围是j-i， 一部分是前l个数，另一部分是l+1到i
dp[l][j-1]+sum[l+1][i],表示前l个数分成j-1块，另外一块分给l+1位置到i位置，也就是l+1到i位置的单词数
*/
            
    printf("%d",dp[plen][k]);
    return 0;
}