- /*
- 每读取一行可以用strcat把字符串连在一起
- 从字符串A中搜索单词word可以用char *p=strstr(A,word);
- 返回NULL则找不到,顺带可以用p-A==0来判断单词是否从A[0]开始匹配。
- 先预处理出w[i][j],表示从i到j的单词数。可以倒着推,w[i][j]=w[i+1][j];
- (如果存在从A[i]字母开始的单词,则w[i][j]=w[i+1][j]+1.出现同一字母开头的多个单词也还是加1就够了.)
- F[i][j]表示前i个字母分成j段得到的最大单词数,答案是F[len][k],
- 可以初始化一下F[i][i]和F[i][1]. 方程F(i,j)=max{ F(r,j-1)+w(r+1,i) (r=j...i-1) }.
- 意思就是把1..r的字母先分成j-1段,剩下的r+1..i的字母分成另一段。
- */
- #include
- #include
- #include
- using namespace std;
- intp,k,s,len,w[2005][2005],f[2005][450];
- charA[2050],str[250],Word[100][2005];
- void Input()
- {
- scanf("%d%d",&p,&k); len=20*p;
- while(getchar()!='\n');
- while(p--)
- {
- scanf("%s",str);
- strcat(&A[1],str);
- }
- scanf("%d",&s);
- while(getchar()!='\n');
- for(inti=1;i<=s;i++) cin>>Word[i];
- }
- inthave(intx,int end)
- {
- for(inti=1;i<=s;i++)
- {
- char*p=strstr(&A[x],Word[i]);
- if(p!=NULL && p-&A[x]==0&& strlen(Word[i])<=end-x+1)return 1;
- }
- return 0;
- }
- void Init()
- {
- for(intj=len;j>0;j--)
- for(inti=j;i>0;i--)
- if(have(i,j)) w[i][j]=w[i+1][j]+1;
- elsew[i][j]=w[i+1][j];
- }
- void DP()
- {
- for(inti=1;i<=k;i++) f[i][i]=f[i-1][i-1]+w[i][i];
- for(inti=1;i<=len;i++) f[i][1]=w[1][i];
- for(inti=1;i<=len;i++)
- for(intj=2;j<=k && j<=i;j++)
- for(intr=j;r)
- f[i][j]=max(f[i][j],f[r][j-1]+w[r+1][i]);
- }
- int main()
- {
- int t;
- cin>>t;
- while(t--)
- {
- Input();
- Init();
- DP();
- printf("%d",f[len][k]);
- }
- return 0;
- }
来源: