第4个和第9个测试点没有过,不知道怎么回事
#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
int p,k;
char a[201];int ax;
int s;
char b[7][201];int bx[7],use[7];
int sum[201][201];
int f[201][201];
int dx[201][41];
int dfs(int,int);
int main()
{
scanf("%d%d\n",&p,&k);
for(int i=0;i<p;i++)
{
for(int j=1;j<=20;j++) scanf("%c",&a[i*20+j]);
scanf("\n");
}
ax=p*20;
scanf("%d",&s);
for(int i=1;i<=s;i++)
{
scanf("%s",b[i]+1);
bx[i]=strlen(b[i]+1);
use[i]=1;
}
/*printf("a[]=\n");
for(int i=1;i<=ax;i++) printf("%c",a[i]);
printf("\n");*/
for(int i=1;i<=s;i++)
{
for(int j=1;j<=s;j++)
{
if(i==j) continue;
if(bx[i]>=bx[j])
{
if(use[i]==0) continue;
int fx=0;
for(int xk=1;xk<=bx[j];xk++)
{
if(b[i][xk]!=b[j][xk])
{
fx=1;
break;
}
}
if(fx==0) use[i]=0;
//如果b[j]是b[i]的前缀,就忽略b[i],use[i]变为0
}
}
}
/*printf("use[]=\n");
for(int i=1;i<=s;i++) printf("%d ",use[i]);
printf("\n");*/
for(int i=1;i<=s;i++)
{
if(use[i]==0) continue;
for(int j=0;j<=ax-bx[i];j++)
{
int fx=1;
for(int xk=1;xk<=bx[i];xk++)
{
if(a[j+xk]!=b[i][xk])
{
fx=0;
break;
}
}
if(fx==1)
{
sum[j+1][j+bx[i]]=1;
//记录有一个从 j+1 到 j+bx[i] 的满足条件的单词
}
}
}
for(int i=1;i<=ax-1;i++)
{
for(int j=i+1;j<=ax;j++)
{
if(sum[i][j-1]==1)
{
sum[i][j]=1;
//sum[i][j]表示以第i个为开始,到第j个及以内是否有单词
}
}
}
for(int i=1;i<=ax;i++)
{
for(int j=i;j<=ax;j++)
{
if(sum[i][j]==1) f[i][j]=1;
}
}
/*printf("sum[][]=\n");
for(int i=1;i<=ax;i++){
for(int j=1;j<=ax;j++) printf("%d ",sum[i][j]);
printf("\n");
}*/
for(int cha=0;cha<ax;cha++)
{
for(int left=1;left+cha<=ax;left++)
{
int right=left+cha;
f[left][right]=max(f[left][right],f[left+1][right]+sum[left][right]);
//f[left][right]表示一整块从left到right的单词个数
}
}
/*printf("f[][]=\n");
for(int i=1;i<=ax;i++){
for(int j=1;j<=ax;j++) printf("%d ",f[i][j]);
printf("\n");
}*/
for(int i=0;i<201;i++)
{
for(int j=0;j<41;j++)
{
dx[i][j]=-1;
}
}
int ans=dfs(1,k);//记忆化搜索求解
printf("%d",ans);
return 0;
}
int dfs(int left,int kk)
{
//dfs(left,kk)或dx[left][kk]表示从left到ax分成kk段的最多单词个数
if(dx[left][kk]!=-1) return dx[left][kk];
if(kk==1)
{
dx[left][kk]=f[left][ax];
return f[left][ax];
}
int res=0;
for(int lr=left;lr+kk-1<=ax;lr++)
{
res=max(res,f[left][lr]+dfs(lr+1,kk-1));
}
dx[left][kk]=res;
return res;
}