蓝杯四十

  算法训练 统计单词个数 

时间限制：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）返回值；

⑦双重循环，三目运算判断是否为总数最大；

⑧输出最大的个数。