题解 P1026 【统计单词个数】

早右昕 · 2017-11-18 07:53:15 · 题解

• 为什么要用哈希呢？它可以判断字符串是否出现(主要是害怕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<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;
}

• 至此，问题得以完美解决.