题解 P1026 【统计单词个数】

其实不需要hash，我们完全可以开一个数组A,对于每一个A[i]表示 原串从i~A[i]是一个能与某个单词匹配的子串。 举个例子 原串:thisisabookyouareaoh 单词:this A[1]=4 表示原串从1~4能匹配某个单词 然后就是DP F[i][j]表示在前i个字符中，分成j段，所含有的最多单词数 根据做题经验——《乘积最大》和一部分的思考可以得出 F[i][j]=max{F[x][j-1]+(t∈[x+1,i]，A[t]<=i的个数)} 解读一下 A[t]<=i 就是找一个位置t，使得有一个从t这个位置开始的串与某个单词匹配并且这个串的终止位置是在我们所给定的区间里的。 再举个例子 原串：thisisabookyouareaoh 单词: thisis 显然A[1]=6,那么如果我们要在第4个字符后面划分出一块， 就是这样—— this/isabookyouareaoh 很明显，在我们划分出的前一块里，因为这个thisis的终止位置不在我们划定的范围内（它的终止位置在“/”之后）,所以不需要增加答案。 我们大可预处理出所有的A[i]（详情看代码） 有个小细节就是，一个位置可以是多个匹配子串的起点，如果真的是这样，那么我们就让这个位置所代表的串尽可能的短，因为只有尽可能的短，这个位置所代表的串才更有可能在某个给定区间中，才更有可能被加入最终答案中。 接下来的问题就是如何快速求出在原串L~R中所有的单词数 转化一下就是 如何快速求出小于等于R的A[i]（L<=i<=R) 这个可以用~~主席树~~我这里就没有那么高端了，对于每一个位置，开一个树状数组，然后先求在[1,R]中小于等于R的A[i]的个数，再求在[1,L-1]中小于等于R的A[i]的个数，然后相减就好了。 具体就这么多，更多的细节还是看代码吧 LuckyCloud ```cpp #include<cstdio> #include<cstring> using namespace std; inline int read() { int cnt=0,f=1;char ch=getchar(); while (ch<'0'||ch>'9'){if (ch=='-')f=-1;ch=getchar();} while (ch>='0'&&ch<='9'){cnt=cnt*10+ch-48;ch=getchar();} return cnt*f; } int len,dp[210][45],p,k,n,t,l[7],a[210],c[210][210]; char s[210],s1[20],word[7][200]; inline int max(int x,int y) { return x>y?x:y; } inline int min(int x,int y) { return x<y?x:y; } inline bool check(int x,int t) { for (int i=t;i<=t+l[x]-1;i++) if (s[i]!=word[x][i-t+1]) return false; return true; } inline int query(int num,int x) { int ret=0; for (;x;x-=x&-x) ret+=c[num][x]; return ret; } int main() { p=read();k=read(); for (int i=1;i<=p;i++) { scanf("%s",s1+1); len=strlen(s1+1); for (int j=1;j<=len;j++) s[++n]=s1[j]; } t=read(); for (int i=1;i<=t;i++) { scanf("%s",word[i]+1); l[i]=strlen(word[i]+1); } memset(a,127/3,sizeof(a)); for (int i=1;i<=t;i++) for (int x=1;x<=n-l[i]+1;x++) if (check(i,x)) a[x]=min(a[x],x+l[i]-1); memset(dp,-1,sizeof(dp)); dp[0][0]=0; for (int i=1;i<=n;i++) { memcpy(c[i],c[i-1],sizeof(c[i])); for (int j=a[i];j<=n;j+=j&-j) c[i][j]++; } for (int i=1;i<=n;i++) for (int j=1;j<=min(i,k);j++) for (int x=0;x<i;x++) if (dp[x][j-1]!=-1) dp[i][j]=max(dp[i][j],dp[x][j-1]+query(i,i)-query(x,i)); printf("%d\n",dp[n][k]); return 0; } ```