题解

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<string>
using namespace std;
int p,n,m,k,dp[210][50],sum[210][210];
string s,a[10];
inline int read(){//读优。。。
int date=0,w=1;char c=0;
while(c<'0'||c>'9'){if(c=='-')w=-1;c=getchar();}
while(c>='0'&&c<='9'){date=date10+c-'0';c=getchar();}
return datew;
}
bool check(int l,int r){//判断是否有单词以s[l]为开头
string x=s.substr(l,r-l+1);//取出字符串
for(int i=1;i<=n;i++)if(x.find(a[i])==0)return true;//查找
return false;
}
void init(){//预处理+读入
string ch;
s+='0';//让下标从1开始
p=read();k=read();
for(int i=1;i<=p;i++){
cin>>ch;
s+=ch;//string除了读入慢，其他啥都好。。。
}
n=read();m=s.length()-1;//记得减1。。。
for(int i=1;i<=n;i++)cin>>a[i];
for(int i=m;i>=1;i--)
for(int j=i;j>=1;j--){//预处理出sum[i][j]
sum[j][i]=sum[j+1][i];
if(check(j,i))sum[j][i];
}
}
void work(){//开始dp
dp[0][0]=0;
for(int i=1;i<=k;i)dp[i][i]=dp[i-1][i-1]+sum[i][i];
for(int i=1;i<=m;i++)dp[i][1]=sum[1][i];//初始化
for(int i=1;i<=m;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]);//转移
printf("%d\n",dp[m][k]);//输出
}
int main(){//主函数3行。。。
init();
work();
return 0;
}