思路与算法

拼接输入各20字母行。对每个起始位置i，找能匹配的最短字典单词终点finish[i]。段[l,r]中的贡献是满足l≤i≤r且finish[i]≤r的起点数，因为同一首字母位置至多选一个词。预处理所有段贡献后，做恰k个非空段的前缀划分DP，枚举最后一段边界取最大。

正确性说明

题目允许词部分重叠，只禁止同一开始位置被选两次。因此给定段内，不同起点相互独立，某起点存在任意完整匹配词便贡献1；最短词能放下当且仅当至少一个词能放下，段贡献准确。任一k段方案有唯一最后切点，前k-1段取最优不会影响本段，DP穷尽所有合法划分，得到最大词数。

复杂度

设L≤200、s≤6，匹配代价按字典实际长度计，含初始化总时间O(L*∑|word|+L³+kL²)，空间O(L²+kL)。

易错点

不能按所有匹配词数累加，同起点多个词只算一次；也不能禁止不同起点词区间重叠。字典中长于整串的词自然不匹配。

参考代码（C++11）

#include <bits/stdc++.h>
using namespace std;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int p, k;
    cin >> p >> k;
    string s, line;
    for (int i = 0; i < p; i++) {
        cin >> line;
        s += line;
    }
    int n = s.size(), m;
    cin >> m;
    vector<string> w(m);
    for (auto &x : w)
        cin >> x;
    vector<int> finish(n, n + 1);
    for (int i = 0; i < n; i++)
        for (auto x : w)
            if (i + (int)x.size() <= n && s.compare(i, x.size(), x) == 0)
                finish[i] = min(finish[i], i + (int)x.size());
    vector<vector<int>> cost(n, vector<int>(n));
    for (int l = 0; l < n; l++)
        for (int r = l; r < n; r++) {
            int cnt = 0;
            for (int i = l; i <= r; i++)
                cnt += finish[i] <= r + 1;
            cost[l][r] = cnt;
        }
    vector<vector<int>> dp(k + 1, vector<int>(n + 1, -100000));
    dp[0][0] = 0;
    for (int g = 1; g <= k; g++)
        for (int i = g; i <= n; i++)
            for (int j = g - 1; j < i; j++)
                dp[g][i] = max(dp[g][i], dp[g - 1][j] + cost[j][i - 1]);
    cout << dp[k][n] << "\n";
}