NC16696. [NOIP2001]统计单词个数
描述
输入描述
每组的第一行有2个正整数(p,k)
p表示字串的行数,k表示分为k个部分。
接下来的p行，每行均有20个字符。
再接下来有1个正整数s，表示字典中单词个数。(1 ≤ s ≤ 6 )
接下来的s行，每行均有1个单词。
输出描述
1个整数，分别对应每组测试数据的相应结果。
示例1
输入:
1 3 thisisabookyouareaoh 4 is a ok sab
输出:
7
C++11(clang++ 3.9) 解法, 执行用时: 13ms, 内存消耗: 748K, 提交时间: 2020-03-04 18:29:34
#include<bits/stdc++.h>
using namespace std;
const int N=2e2+9;
string s,a[10];
int f[N][N],sum[N][N],n;
bool ok(int l,int r)
{
string x=s.substr(l,r-l+1);
for(int i=0;i<n;i++)
if(x.find(a[i])==0)
return 1;
return 0;
}
int main()
{
int p,K;
cin>>p>>K;
for(int i=0;i<p;i++)
{
string ss;
cin>>ss;
s+=ss;
}
cin>>n;
for(int i=0;i<n;i++)
cin>>a[i];
for(int i=s.size()-1;~i;i--)
{
for(int j=i;~j;j--)
{
sum[j][i]=sum[j+1][i];
if(ok(j,i))
sum[j][i]++;
}
f[i][1]=sum[0][i];
}
for(int k=1;k<=K;k++)
for(int i=0;s[i];i++)
for(int j=k-1;j<i;j++)
f[i][k]=max(f[i][k],f[j][k-1]+sum[j+1][i]);
cout<<f[s.size()-1][K]<<endl;
return 0;
}