统计单词个数-摩杜云开发者社区

[NOIP2001 提高组] 统计单词个数

题目描述

给出一个长度不超过统计单词个数_数据的由小写英文字母组成的字母串（该字串以每行统计单词个数_字符串_02 个字母的方式输入，且保证每行一定为个）。要求将此字母串分成统计单词个数_字符串_04 份，且每份中包含的单词个数加起来总数最大。

每份中包含的单词可以部分重叠。当选用一个单词之后，其第一个字母不能再用。例如字符串 this 中可包含 this 和 is，选用 this 之后就不能包含 th。

单词在给出的一个不超过统计单词个数_数据_05 个单词的字典中。

要求输出最大的个数。

输入格式

每组的第一行有两个正整数统计单词个数_测试数据_06 。统计单词个数_数据_07 表示字串的行数，统计单词个数_字符串_04 表示分为个部分。

接下来的统计单词个数_数据_07 行，每行均有统计单词个数_字符串_02 个字符。

再接下来有一个正整数统计单词个数_数据_12 ，表示字典中单词个数。接下来的行，每行均有一个单词。

输出格式

统计单词个数_字符串_14 个整数，分别对应每组测试数据的相应结果。

样例 #1

样例输入 #1

1 3
thisisabookyouareaoh
4
is
a
ok
sab

样例输出 #1

提示

【数据范围】
对于统计单词个数_字符串_15 的数据，统计单词个数_数据_16 ，统计单词个数_字符串_17 。

【样例解释】划分方案为 this / isabookyoua / reaoh

【题目来源】

NOIP 2001 提高组第三题

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

const int mod=100003;
int n,m,p,K,f[210][210],s[210][210];;
bool vis[mod],v[210];
char a[210],d[10][210];

int hash(char \*str) {
    int k=0,ln=strlen(str+1);
    for(int i=1; i<=ln; i++) {
        k=k\*29+str[i];
        if(k>=mod) k%=mod;
    }
    return  k;
}

int main() {
    scanf("%d%d",&p,&K);
    for(int i=1,c=1; i<=p; i++) {
        scanf("%s",&a[c]);
        c+=20;
    }
    n=p\*20;
    scanf("%d",&m);
    for(int i=1,h; i<=m; i++) {
        scanf("%s",&d[i][1]);
        h=hash(d[i]);
        if(vis[h]) i--,m--;
        else vis[h]=1;
    }
    for(int i=1; i<=n; i++) {
        for(int j=1; j<=n; j++) {
            memset(v,0,sizeof v);
            for(int k=1; k<=m; k++) {
                int ln=strlen(d[k]+1);
                for(int l=i; l+ln-1<=j; l++) {
                    if(v[l]) continue;
                    bool flag=0;
                    for(int r=1; r<=ln; r++) {
                        if(a[l+r-1]!=d[k][r]) {
                            flag=1;
                            break;
                        }
                    }
                    if(!flag) s[i][j]++,v[l]=1;
                }
            }
        }
    }
    for(int k=1; k<=K; k++) {
        for(int i=1; i<=n; i++) {
            for(int j=k-1; j<=i-1; j++) {
                f[i][k]=max(f[i][k],f[j][k-1]+s[j+1][i]);
            }
        }
    }
    printf("%d\n",f[n][K]);
    return 0;
}