蓝桥杯算法训练VIP-统计单词个数 （C++代码）

解题思路:

为什么要用哈希呢？它可以判断字符串是否出现(主要是害怕TLE).

这里用的字符串哈希是把str当作一个base进制数处理，因为字母有26个（废话），所以这里选用29这个稍大一些的质数作为基数，顺便取个膜100003（而不是100007或100009什么的）

至于dp就很简单了（写给像我一样看不懂题解的蒟蒻们），设f[i][k]为前i个字符分成了k断的最优解，显然状态可以这样转移:f[i][k]=max{f[j][k-1]+s[j+1][i],k-1<=j<i}.s[l][r]表示从l->r有多少个单词（可以暴力预处理），若过一段分成了k小段，那么这一段至少有k个字符（废话），这就是j要大于等于k-1的原因.

好了，看代码：

注意事项:





参考代码:

#include<cstdio>
#include<cstring>
#include<string>
#include<cmath>
#include<algorithm>
#include<iostream>
using namespace std;
int len=0;
char zfc[300];
int p,k;
char wl;
void dr()//读入
{    while(p--)//p没有用了……
    {    
    for(int i=0;i<20;i++)//每行20个
        {            scanf(" %c",&wl);//注意有空格——" %c"
            zfc[len++]=wl;//将新的字符加入到大字符串中
        }
    }
}char dt[10][300]={0};//存每个可以使用的匹配单词，即字典int gs;//字典单词个数
    int kmp[10][300]={0};//kmp匹配函数int ln[10];
    //存字典中每个单词的长度
    bool visit[300];//防止重复统计，即题意中的“不能重复开头”
    int xx[10];//每个单词目前匹配的位数，具体在KMP函数中int sum;
    //统计一段单词中可以匹配的总个数
    int ct(int zuo,int you)//KMP函数（匹配函数）{
    sum=0;    
    memset(visit,false,sizeof(visit));    
    memset(xx,0,sizeof(xx));    
    for(int i=zuo;i<=you;i++)
    {        for(int j=0;j<gs;j++)
        {            while(xx[j]&&zfc[i]!=dt[j][xx[j]])xx[j]=kmp[j][xx[j]];            if(zfc[i]==dt[j][xx[j]])xx[j]++;//KMP过程
            if(xx[j]==ln[j]&&!visit[i-ln[j]+1])//已经匹配到全部，且开头未被统计过
            {
                visit[i-ln[j]+1]=true;
                sum++;//计数
            }
        }
    }    return sum;//返回计数
    }
    int main()
    {    scanf("%d%d",&p,&k);
    dr();    
    scanf("%d",&gs); 
    for(int i=0;i<gs;i++)scanf("%s",dt[i]);//读入
    int x;    
    for(int i=0;i<gs;i++)//KMP匹配序列生成
    {
        kmp[i][0]=kmp[i][1]=0;
        ln[i]=strlen(dt[i]);
        x=0;        for(int j=1;j<ln[i];j++)
        {            while(x&&dt[i][x]!=dt[i][j])x=kmp[i][x];
            kmp[i][j+1]=dt[i][x]==dt[i][j]?++x:0;
        }
    }    int f[300][300]={0};    
            for(int i=0;i<len;i++)
    {        for(int j=1;j<=k;j++)
        {            if(j==1)
            {
                f[i][j]=ct(0,i);//一段直接匹配
            }            else
            {                for(int k=0;k<i;k++)
                {                    if(f[k][j-1])
                    f[i][j]=max(f[i][j],f[k][j-1]+ct(k+1,i));//取最大值
                }
            }
        }
    }    printf("%d",f[len-1][k]);//输出
    return 0;
}