#P1026. [NOIP2001 提高组] 统计单词个数

    ID: 1788 Type: RemoteJudge 1000ms 128MiB Tried: 0 Accepted: 0 Difficulty: (None) Uploaded By: Tags>字符串动态规划,dp2001NOIp 提高组枚举

[NOIP2001 提高组] 统计单词个数

题目描述

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

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

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

要求输出最大的个数。

输入格式

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

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

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

输出格式

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

1 3
thisisabookyouareaoh
4
is
a
ok
sab

7

提示

【数据范围】
对于 100%100\% 的数据,2k402 \le k \le 401s61 \le s \le 6

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

【题目来源】

NOIP 2001 提高组第三题