https://www.luogu.com.cn/problem/P1026
这题的idea首先是直接暴力枚举k，发现会t，遂想到dp
用 \(dp[i][k]\) 表示 前 \(i\) 个数形成了 \(k\) 段数字的最大答案
注意一个比较坑的点是可能同一个位置会有多个单词开始，但是只计数一个
eg：
1 2
then
2
the
then
答案应该是 1
贴code（写的比较丑）：
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 1e5 + 10;
string str, s;
int p, k, n, x;
vector<string> v;
int dp[202][44];
int pre[202][202];
inline bool check(int l, int r) {
string tem = s.substr(l, r - l + 1);
for(auto x : v) {
if(r - l + 1 >= x.size()) {
if(tem.find(x) == 0) return 1;
}
}
return 0;
}
void init() { // 预处理pre[l, r]
for(int r = n; r >= 1; r--) { // r 也可以从前往后
for(int l = r; l >= 1; l--) {
pre[l][r] = pre[l + 1][r];
if(check(l, r)) pre[l][r]++;
}
}
}
int main() {
cin >> x >> k;
while(x--) {
cin >> str;
s += str;
}
s = " " + s;
n = s.size() - 1;
if(k > n - 1) {
puts("0");
return 0;
}
cin >> p;
for(int i = 1; i <= p; i++) {
cin >> str;
v.push_back(str);
}
init();
for(int K = 1; K <= k; K++) { // K <= k
for(int i = 1; i <= n; i++) { // i < n
for(int j = K - 1; j < i; j++) {
dp[i][K] = max(dp[i][K], dp[j][K - 1] + pre[j + 1][i]);
}
// cout << "i: " << i << " k: " << K << "dp[i][K]: " << dp[i][K] << endl;
}
}
cout << dp[n][k] << endl;
return 0;
}