统计单词个数

题目
将一个字符串切K刀后求字典中的词语出现的次数

两个词语不能第一个字母在字符串中出现的位置相同

算法
DP，f[i][j]表示枚举到第i个，前面切了j刀

调试记录
本来用Hash，调了一个下午没过

然后直接用string，然后就过了

代码

#include <iostream> #include <cstdio> #include <functional> using std::cin; using std::string; using std::max; using std::min; string s,a[10]; int n,dp[500][500]={0},sum[500][500]={0}; bool check(int l,int r){ string t=s.substr(l,r-l+1); for(int i=1;i<=n;i++) if(t.find(a[i])==0) return true; return false; } int main(){ int p,k; scanf("%d%d",&p,&k); s+=' '; for(int i=1;i<=p;i++){ string t; cin >> t; s+=t; } int m=s.length()-1; scanf("%d\n",&n); for(int i=1;i<=n;i++) cin >> a[i]; for(int i=m;i>=1;i--) for(int j=i;j>=1;j--){ sum[j][i]=sum[j+1][i]; if(check(j,i)) sum[j][i]++; } dp[0][0]=0; for(int i=1;i<=k;i++) dp[i][i]=dp[i-1][i-1]+sum[i][i]; for(int i=1;i<=m;i++) dp[i][1]=sum[1][i]; for(int i=1;i<=m;i++) for(int j=1;j<=k && j<i;j++) for(int t=j;t<i;t++) dp[i][j]=max(dp[i][j],sum[t+1][i]+dp[t][j-1]); printf("%d\n",dp[m][k]); return 0; }cpp