首页 > 代码库 > 洛谷 【P1026】统计单词个数
洛谷 【P1026】统计单词个数
P1026 统计单词个数
题目描述
给出一个长度不超过200的由小写英文字母组成的字母串(约定;该字串以每行20个字母的方式输入，且保证每行一定为20个)。要求将此字母串分成k份(1<k<=40)，且每份中包含的单词个数加起来总数最大(每份中包含的单词可以部分重叠。当选用一个单词之后，其第一个字母不能再用。例如字符串this中可包含this和is，选用this之后就不能包含th)。
单词在给出的一个不超过6个单词的字典中。
要求输出最大的个数。
输入输出格式
输入格式：
每组的第一行有二个正整数(p，k)
p表示字串的行数;
k表示分为k个部分。
接下来的p行，每行均有20个字符。
再接下来有一个正整数s，表示字典中单词个数。(1<=s<=6)
接下来的s行，每行均有一个单词。
输出格式：
一个整数，分别对应每组测试数据的相应结果。
输入输出样例
输入样例#1：
1 3thisisabookyouareaoh4isaoksab
输出样例#1：
7
说明
this/isabookyoua/reaoh
喜闻乐见的Code
#include<cstdio>#include<cstring>using namespace std;char a[205],word[10][205];int w[205][205],f[205][45],len[10],d[205];int main() { int n,k,m; scanf("%d%d",&n,&k); for(int i=0;i<n;i++) scanf("%s",a+1+20*i); n*=20; scanf("%d",&m); for(int i=0;i<m;i++) { scanf("%s",word[i]); len[i]=strlen(word[i]); } for(int i=1;i<=n;i++) for(int j=0;j<m;j++) if(strncmp(&a[i],word[j],len[j])==0&&(d[i]==0||d[i]>len[j])) d[i]=len[j]; for(int i=1;i<=n;i++) for(int j=i;j<=n;j++) { w[i][j]=w[i][j-1]; for(int _=i;_<=j;_++) w[i][j]+=d[_]==(j-_+1)?1:0; } for(int i=1;i<=k;i++) for(int j=i;j<=n;j++) for(int _=i-1;_<j;_++) if(f[j][i]<f[_][i-1]+w[_+1][j]) f[j][i]=f[_][i-1]+w[_+1][j]; printf("%d",f[n][k]); return 0;}
洛谷 【P1026】统计单词个数
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。