题解 P1026 【统计单词个数】
whyl
2019-10-05 19:25:08
一年前看着道题不会做。。。。
（其实这道题一点也不难。。。）
复仇成功。。。。。。。。
暴力跑出对于没一段去间造成的贡献。。
复杂度（n^3*s*lenth[i]）的
但实际上远远跑不满
在用dp解决
定义状态dp[i][j]表示到i个字符
分割成j段的最大ans
转移方程 dp[i][j]=dp[k][j-1]+sum[k+1][i]
未免太过显然。。。
放代码
```
#include<bits/stdc++.h>
using namespace std;
int n,m,s,len,sum[205][205],lenth[11],f[205][55];
string a,b;
string ss[11];
inline void read(){
cin>>n>>m;
for(int i=1;i<=n;i++){
cin>>b;
a=a+b;
}
cin>>s;
len=a.length();
for(int i=1;i<=s;i++) cin>>ss[i];
for(int i=1;i<=s;i++) lenth[i]=ss[i].length();
}
inline void pre_work(){
for(int i=0;i<len;i++)
for(int j=i;j<len;j++)
for(int k=i;k<=j;k++){
int flag=1;
for(int l=1;l<=s;l++){
if(k+lenth[l]-1>j) continue;
for(int w=0;w<lenth[l];w++){
// if(i==0&&j==3&&k==3&&l==1){
// cout<<a[k+w]<<" "<<ss[l][w]<<endl;
// }
if(w==lenth[l]-1&&a[k+w]==ss[l][w]){
flag=0;
break;
}
if(a[k+w]!=ss[l][w]) break;
}
if(flag==0) break;
}
if(flag==0) sum[i][j]++;
}
// cout<<sum[0][3]<<endl;
// for(int i=0;i<len;i++) {
// for(int j=0;j<len;j++)
// cout<<sum[i][j]<<" ";
// cout<<endl;
// }
}
inline void solve(){
for(int i=0;i<len;i++){
f[i][1]=sum[0][i];
for(int j=0;j<i;j++)
for(int k=2;k<=min(m,j+1);k++){
f[i][k]=max(f[i][k],f[j][k-1]+sum[j+1][i]);
}
}
cout<<f[len-1][m]<<endl;
}
int main(){
read();
pre_work();
solve();
return 0;
}
```