[NOIP 2001 提高组] 统计单词个数

Luogu
IDLGP1026
Time1000ms
Memory128MB
DifficultyP4
字符串动态规划 DP2001NOIP 提高组枚举区间 DP
给出一个长度不超过 $200$ 的由小写英文字母组成的字母串(该字串以每行 $20$ 个字母的方式输入,且保证每行一定为 $20$ 个)。要求将此字母串分成 $k$ 份,且每份中包含的单词个数加起来总数最大。 每份中包含的单词可以部分重叠。当选用一个单词之后,其第一个字母不能再用。例如字符串 `this` 中可包含 `this` 和 `is`,选用 `this` 之后就不能包含 `th`。 单词在给出的一个不超过 $6$ 个单词的字典中。 要求输出最大的个数。 ## Input 每组的第一行有两个正整数 $p,k$。 $p$ 表示字串的行数,$k$ 表示分为 $k$ 个部分。 接下来的 $p$ 行,每行均有 $20$ 个字符。 再接下来有一个正整数 $s$,表示字典中单词个数。 接下来的 $s$ 行,每行均有一个单词。 ## Output $1$个整数,分别对应每组测试数据的相应结果。 [samples] ## Note **【数据范围】** 对于 $100\%$ 的数据,$2 \le k \le 40$,$1 \le s \le 6$。 **【样例解释】** 划分方案为 this / isabookyoua / reaoh **【题目来源】** NOIP 2001 提高组第三题
Samples
Input #1
1 3
thisisabookyouareaoh
4
is
a
ok
sab
Output #1
7
API Response (JSON)
{
  "problem": {
    "name": "[NOIP 2001 提高组] 统计单词个数",
    "description": {
      "content": "给出一个长度不超过 $200$ 的由小写英文字母组成的字母串(该字串以每行 $20$ 个字母的方式输入,且保证每行一定为 $20$ 个)。要求将此字母串分成  $k$ 份,且每份中包含的单词个数加起来总数最大。   每份中包含的单词可以部分重叠。当选用一个单词之后,其第一个字母不能再用。例如字符串 `this` 中可包含 `this` 和 `is`,选用 `this` 之后就不能包含  `th`",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 131072
    },
    "difficulty": {
      "LuoguStyle": "P4"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP1026"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "给出一个长度不超过 $200$ 的由小写英文字母组成的字母串(该字串以每行 $20$ 个字母的方式输入,且保证每行一定为 $20$ 个)。要求将此字母串分成\n $k$ 份,且每份中包含的单词个数加起来总数最大。  \n\n每份中包含的单词可以部分重叠。当选用一个单词之后,其第一个字母不能再用。例如字符串 `this` 中可包含 `this` 和 `is`,选用 `this` 之后就不能包含\n `th`...",
      "is_translate": false,
      "language": "English"
    }
  ]
}
Full JSON Raw Segments