```c++
#include<cstdio>
#include<cstdlib>
#include<math.h>
#include<string.h>
#include<queue>
#define INF 1e9
using namespace std;
const int maxn=210;
const int maxk=50;
const int maxm=10;
char str[maxn],word[maxm][maxn],a,sss[maxn];
int n,K,m,l,N;
int f[maxn][maxk],g[maxn][maxn],d[maxn];
int trie[maxn*maxm][30],val[maxn*maxm],tl,num[maxn*maxm];
/// trie
void build_trie(int x)
{
int u=0;
for(int i=0;i<strlen(word[x]);i++)
{
int v=int(word[x][i]-'a');
if(trie[u][v]==0)
{
++tl;
memset(trie[tl],0,sizeof(trie[tl]));
val[tl]=0;
trie[u][v]=tl;
}
u=trie[u][v];
num[u]=i+1;
}
val[u]=1;
}
int find_trie(int x)
{
int ans=INF;
int u=0;
for(int i=x;i<=l;i++)
{
int v=int(str[i]-'a');
if(!trie[u][v]) break;
u=trie[u][v];
if(val[u]) return num[u];
}
//printf("{%d} ",x);
return -x;
}
///
int main()
{
scanf("%d",&N);
while(N--)
{
scanf("%d%d",&n,&K);
l=0;
for(int i=1;i<=n;i++)
{
scanf("%s",sss);
for(int j=0;j<20;j++)
str[++l]=sss[j];
}
scanf("%d",&m);
for(int i=1;i<=m;i++)
{
scanf("%s",word[i]);
build_trie(i);
}
int u=0;
for(int i=1;i<=l;i++)
d[i]=find_trie(i)+i-1;
for(int i=0;i<l;i++)
for(int j=1;j<=l-i;j++)
for(int k=j;k<=i+j;k++)
if(d[k]!=-1&&d[k]<=i+j)
g[j][i+j]++;
for(int i=1;i<=l;i++) f[i][1]=g[1][i];
for(int k=2;k<=K;k++)
{
for(int i=k;i<=l;i++)
for(int j=k;j<i;j++)
f[i][k]=max(f[i][k],f[j][k-1]+g[j+1][i]);
}
printf("%d",f[l][K]);
}
return 0;
}
```
by YKgsmUDq @ 2017-10-18 12:35:21
```cpp
#include<cstdio>
#include<cstdlib>
#include<math.h>
#include<string.h>
#include<queue>
#define INF 1e9
using namespace std;
const int maxn=210;
const int maxk=50;
const int maxm=10;
char str[maxn],word[maxm][maxn],a,sss[maxn];
int n,K,m,l,N;
int f[maxn][maxk],g[maxn][maxn],d[maxn];
int trie[maxn*maxm][30],val[maxn*maxm],tl,num[maxn*maxm];
/// trie
void build_trie(int x)
{
int u=0;
for(int i=0;i<strlen(word[x]);i++)
{
int v=int(word[x][i]-'a');
if(trie[u][v]==0)
{
++tl;
memset(trie[tl],0,sizeof(trie[tl]));
val[tl]=0;
trie[u][v]=tl;
}
u=trie[u][v];
num[u]=i+1;
}
val[u]=1;
}
int find_trie(int x)
{
int ans=INF;
int u=0;
for(int i=x;i<=l;i++)
{
int v=int(str[i]-'a');
if(!trie[u][v]) break;
u=trie[u][v];
if(val[u]) return num[u];
}
//printf("{%d} ",x);
return -x;
}
///
int main()
{
scanf("%d",&N);
while(N--)
{
scanf("%d%d",&n,&K);
l=0;
for(int i=1;i<=n;i++)
{
scanf("%s",sss);
for(int j=0;j<20;j++)
str[++l]=sss[j];
}
scanf("%d",&m);
for(int i=1;i<=m;i++)
{
scanf("%s",word[i]);
build_trie(i);
}
int u=0;
for(int i=1;i<=l;i++)
d[i]=find_trie(i)+i-1;
for(int i=0;i<l;i++)
for(int j=1;j<=l-i;j++)
for(int k=j;k<=i+j;k++)
if(d[k]!=-1&&d[k]<=i+j)
g[j][i+j]++;
for(int i=1;i<=l;i++) f[i][1]=g[1][i];
for(int k=2;k<=K;k++)
{
for(int i=k;i<=l;i++)
for(int j=k;j<i;j++)
f[i][k]=max(f[i][k],f[j][k-1]+g[j+1][i]);
}
printf("%d",f[l][K]);
}
return 0;
}
```
by YKgsmUDq @ 2017-10-18 12:39:17
scanf("%d",&N);
while(N--)
本题只有一组数据 不是多组
by TakaML @ 2017-10-27 19:46:48