算法训练 统计单词个数
时间限制：1.0s 内存限制：256.0MB
问题描述
给出一个长度不超过200的由小写英文字母组成的字母串(约定;该字串以每行20个字母的方式输入，且保证每行一定为20个)。要求将此字母串分成k份 (1<k<=40)，且每份中包含的单词个数加起来总数最大(每份中包含的单词可以部分重叠。当选用一个单词之后，其第一个字母不能再用。例 如字符串this中可包含this和is，选用this之后就不能包含th)。
单词在给出的一个不超过6个单词的字典中。
要求输出最大的个数。
输入格式
第一行有二个正整数(p，k)
p表示字串的行数;
k表示分为k个部分。
接下来的p行，每行均有20个字符。
再接下来有一个正整数s，表示字典中单词个数。(1<=s<=6)
接下来的s行，每行均有一个单词。
输出格式
每行一个整数，分别对应每组测试数据的相应结果。
样例输入
1 3
thisisabookyouareaoh
4
is
a
ok
sab
样例输出
7
数据规模和约定
长度不超过200，1<k<=40，字典中的单词数不超过6。
#include <stdio.h>
#include <string.h>
#define InfiniteMin -999999999
int p,k,s;
char str[10][21];
char word[6][16];
int flag[6];
int Cnt[201][201];
int getCnt(int a,int b)
{
int i,j,m,count=0;
if(Cnt[a][b]<=0)
{
for (i=a;i<=b;i++)
for (j=0;j<s;j++)
if(word[j][0]==str[i/20][i%20])
{
for(m=1;word[j][m]!='\0'&&i+m<=b;m++)
if(word[j][m]!=str[(i+m)/20][(i+m)%20])
break;
if(word[j][m]=='\0')
{
count++;
break;
}
}
Cnt[a][b]=count;
}
return Cnt[a][b];
}
int main()
{
int i,u,K;
int max,temp;
int F[201][41];
scanf("%d%d",&p,&k);
for(i=0;i<p;i++)
scanf("%s",str[i]);
scanf("%d",&s);
for(i=0;i<s;i++)
scanf("%s",word[i]);
for(i=0;i<20*p;i++)
F[i][1]=getCnt(0,i);
for(K=2;K<=k;K++)
for(i=k;i<p*20;i++)
{
max=InfiniteMin;
for(u=K-1;u<=i-1;u++)
{
temp=F[u][K-1]+getCnt(u+1,i);
max=max>temp?max:temp;
}
F[i][K]=max;
}
printf("%d",F[p*20-1][k]);
return 0;
}
思路分析：
①定义变量：行数，部分，单词个数，字符串（二维数组），循环次数，最大的个数；
②输入行数，部分；
③for语句循环输入字符；
④输入单词个数；
⑤for语句循环输入单词；
⑥for语句调用函数（两个形参）：
（1）定义变量：循环次数；
（2）根据题中所给要求进行循环判断；
（3）返回值；
⑦双重循环，三目运算判断是否为总数最大；
⑧输出最大的个数。
网友评论