1 条题解
-
0
【本题解由站长编写】
先把 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
- 上传者