跳至正文

1 条题解

  • 0
    @ 2026-10-7 23:01:14

    【本题解由站长编写】

    先把 p 行拼成完整字符串。cnt(l,r) 表示区间 [l,r) 内能匹配到的单词数(某个位置只要有字典单词以它开头且整个单词落在区间内就计一次,重叠允许、起点不重复)。DP:f[j][i] = 前 i 个字符分成 j 段的最大单词数,转移枚举上一段的起点。

    代码(C++17)

    #include <bits/stdc++.h>
    using namespace std;
    int main() {
        int p, k;
        cin >> p >> k;
        string s;
        for (int i = 0; i < p; i++) { string t; cin >> t; s += t; }
        int sn;
        cin >> sn;
        vector<string> dict(sn);
        for (auto &w : dict) cin >> w;
        int L = s.size();
        vector<vector<int>> cnt(L, vector<int>(L + 1, 0));
        for (int l = 0; l < L; l++) {
            int c = 0;
            for (int r = l + 1; r <= L; r++) {
                for (auto &wd : dict)
                    if (r - l >= (int)wd.size() && s.compare(r - wd.size(), wd.size(), wd) == 0 && r - wd.size() >= l) { c++; break; }
                cnt[l][r] = c;
            }
        }
        vector<vector<int>> f(k + 1, vector<int>(L + 1, 0));
        for (int j = 1; j <= k; j++)
            for (int i = 1; i <= L; i++)
                for (int t = j - 1; t < i; t++)
                    f[j][i] = max(f[j][i], f[j - 1][t] + cnt[t][i]);
        cout << f[k][L] << endl;
        return 0;
    }
    
    • 1

    信息

    ID
    4308
    时间
    1000ms
    内存
    256MiB
    难度
    5
    标签
    递交数
    0
    已通过
    0
    上传者