题解：P1026 [NOIP 2001 提高组] 统计单词个数
WA_WonderfulAnswer
·
·
题解
前言
update on 2025.9.1：修复了 \LaTeX 显示错乱的问题。
题目要求
给出一个长度不超过 200 的由小写英文字母组成的字母串（该字串以每行 20 个字母的方式输入，且保证每行一定为 20 个）。要求将此字母串分成
# dp 推导
为方便下文描述，定义 $cnt_{i,j}$ 表示字符串中从第 $i$ 个字符到第 $j$ 个字符的子串（$1 \leq i \leq j \leq n$，$n$ 为字符串总长度）能统计到的最大单词数。
## 初始化
由于单词统计规则（选用后第一个字母不可再用），子串 $[i,j]$ 的最优解依赖于子串 $[i+1,j]$ 的最优解，因此采用 从后往前 的遍历顺序（$i$ 从 $n$ 到 $1$，$j$ 从 $i$ 到 $n$）：
- 初始情况（子串长度为 $1$）：若 $i = j$，则 $cnt_{i,j} = 1$，当且仅当该字符是字典中的单词；否则 $cnt_{i,j}=0$。
- 一般情况（子串长度 $>1$）：
+ 不使用以 $i$ 开头的单词：此时 $cnt_{i,j}$ 直接继承 $cnt_{i+1,j}$（即从 $i+1$ 开始统计子串 $[i+1,j]$ 的单词数）。
+ 使用以 $i$ 开头的单词：检查是否存在字典中的单词以 $i$ 开头且完全包含在 $[i,j]$ 内。若存在，则 $cnt_{i,j} = \max(cnt_{i,j}, 1 + cnt_{i+1,j})$（选此单词得 $1$ 分，后续从 $i+1$ 开始统计，因 $i$ 已被使用）。
## dp 状态与转移推导
### 状态定义
定义 $dp_{i,j}$ 表示将字符串的前 $i$ 个字符（$1 \leq i \leq n$）分成 $j$ 份（$1 \leq j \leq k$）时，能得到的最大单词总数。所以，求前 $i$ 个字符分 $j$ 份的最优解，可依赖前 $m$ 个字符分 $j-1$ 份的最优解（$m < i$）。
### 边界条件
当 $j=1$（仅分 $1$ 份）时，前 $i$ 个字符的最大单词数就是整个子串 $[1,i]$ 的最大单词数——因为没有分割，直接使用预处理好的 $cnt_{1,i}$。因此边界条件为：
$$\large dp_{i,1} = cnt_{1,i} \quad (1 \leq i \leq n)$$
### 状态转移方程
当 $j \geq 2$ 时，需考虑“如何将前 $i$ 个字符分成 $j$ 份”。我们可以先将前 $m$ 个字符分成 $j-1$ 份（$m$ 为前 $j-1$ 份的结束位置），再将第 $m+1$ 到 $i$ 个字符作为第 $j$ 份。此时需满足“每份至少 $1$ 个字符”的约束，即前 $j-1$ 份至少需要 $j-1$ 个字符，故 $m \geq j-1$；第 $j$ 份至少需要 $1$ 个字符，故 $m < i$。
不难得出 $m \in \left[j-1,i-1\right]$。对于每个合法的 $m$，前 $j-1$ 份的最大单词数为 $dp_{m,j-1}$，第 $j$ 份的最大单词数为 $cnt_{m+1,i}$，总单词数为两者之和。取所有可能 $m$ 对应的最大值，即为 $dp_{i,j}$ 的结果。
最终状态转移方程为：
$$\large dp_{i,j} = \max_{m \in [j-1, i-1]} \{dp_{m,j-1} + cnt_{m+1,i} \} \quad (2 \leq j \leq k, j \leq i \leq n)$$
# 时间复杂度
- 预处理 $cnt$ 数组：$i$ 遍历 $n$ 次，$j$ 遍历 $n$ 次，每次检查单词的最大长度为 $L$（字典中最长单词长度），复杂度为 $O(n^2 L)$。
- dp 计算：$j$ 遍历 $k$ 次，$i$ 遍历 $n$ 次，$m$ 遍历 $n$ 次，复杂度为 $O(kn^2)$。
总时间复杂度为 $O(n^2 (L + k))$。对于本题的数据范围，该时间复杂度可以通过，~~不需要吸氧。~~
# 细节决定成败
本题前三个数据的换行符是 `\r\n`，这就会导致 `getline` 挂掉。对于本题的数据，我们应该使用 `cin` 来读入字符串。
P.S.`cin.tie()->sync_with_stdio(0);` 是个好东西。
# AC Code
码风不好，不喜勿喷。
```cpp
#include <bits/stdc++.h>
using namespace std;
int p, k, m;
char s[205], dic[10][25];
int sz[10], mlen, dp[205][45], cnt[205][205];
string readstr(int p) {
string res = "", tmp = "";
for (int i = 1; i <= p; i++) {
cin >> tmp;
res += tmp;
}
return res;
}
bool check(int a, int b) {
int l = b - a + 1;
if (l > mlen) return false;
for (int i = 0; i < m; i++) {
if (sz[i] != l) continue;
bool ok = true;
for (int j = 0; j < l; j++) {
if (s[a + j] != dic[i][j]) {
ok = false;
break;
}
}
if (ok) return true;
}
return false;
}
void init() {
int n = strlen(s + 1);
for (int i = n; i >= 1; i--) {
cnt[i][i] = 0;
if (check(i, i)) cnt[i][i] = 1;
for (int j = i + 1; j <= n; j++) {
cnt[i][j] = cnt[i + 1][j];
for (int l = 1; l <= mlen && i + l - 1 <= j; l++) {
if (check(i, i + l - 1)) {
cnt[i][j] = max(cnt[i][j], 1 + cnt[i + 1][j]);
break;
}
}
}
}
}
int main() {
cin.tie()->sync_with_stdio(0);
cin >> p >> k;
string tmp = readstr(p);
int len = tmp.size();
for (int i = 0; i < len; i++) {
s[i + 1] = tmp[i];
}
s[len + 1] = '\0';
cin >> m;
mlen = 0;
for (int i = 0; i < m; i++) {
cin >> dic[i];
sz[i] = strlen(dic[i]);
if (sz[i] > mlen) mlen = sz[i];
}
init();
int n = strlen(s + 1);
for (int i = 1; i <= n; i++) {
dp[i][1] = cnt[1][i];
}
for (int j = 2; j <= k; j++) {
for (int i = j; i <= n; i++) {
dp[i][j] = 0;
for (int m = j - 1; m < i; m++) {
dp[i][j] = max(dp[i][j], dp[m][j - 1] + cnt[m + 1][i]);
}
}
}
cout << dp[n][k] << endl;
return 0;
}
```
# 结语
码字不易，点个赞再走呗~