洛谷P1026 统计单词个数

题目描述

给出一个长度不超过 200200 的由小写英文字母组成的字母串（该字串以每行 2020 个字母的方式输入，且保证每行一定为 2020 个）。要求将此字母串分成 kk 份，且每份中包含的单词个数加起来总数最大。

每份中包含的单词可以部分重叠。当选用一个单词之后，其第一个字母不能再用。例如字符串 this 中可包含 this 和 is，选用 this 之后就不能包含 th。

单词在给出的一个不超过 66 个单词的字典中。

要求输出最大的个数。

输入格式

每组的第一行有两个正整数 p,kp,k。 pp 表示字串的行数，kk 表示分为 kk 个部分。

接下来的 pp 行，每行均有 2020 个字符。

再接下来有一个正整数 ss，表示字典中单词个数。 接下来的 ss 行，每行均有一个单词。

输出格式

11个整数，分别对应每组测试数据的相应结果。

输入输出样例

输入 #1复制

1 3
thisisabookyouareaoh
4
is
a
ok
sab

输出 #1复制

7

说明/提示

【数据范围】
对于 100\%100% 的数据，2 \le k \le 402≤k≤40，1 \le s \le 61≤s≤6。

【样例解释】 划分方案为 this / isabookyoua / reaoh

【题目来源】

NOIP 2001 提高组第三题

上代码：

#include
#include
#include
#include
#include
using namespace std;
int p,n,m,k,dp[210][50],sum[210][210];
string s,a[10];
inline int read(){//读优。。。int date=0,w=1;char c=0;while(c<'0'||c>'9'){if(c=='-')w=-1;c=getchar();}while(c>='0'&&c<='9'){date=date*10+c-'0';c=getchar();}return date*w;
}
bool check(int l,int r){//判断是否有单词以s[l]为开头string x=s.substr(l,r-l+1);//取出字符串for(int i=1;i<=n;i++)if(x.find(a[i])==0)return true;//查找return false;
}
void init(){//预处理+读入string ch;s+='0';//让下标从1开始p=read();k=read();for(int i=1;i<=p;i++){cin>>ch;s+=ch;//string除了读入慢，其他啥都好。。。}n=read();m=s.length()-1;//记得减1。。。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[i][j]sum[j][i]=sum[j+1][i];if(check(j,i))sum[j][i]++;}
}
void work(){//开始dpdp[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

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！