@[ruanwentao666](/user/782700) 我的AC代码（DP，仅供参考）：
```cpp
#include<bits/stdc++.h>
using namespace std;
int p, n, m, dp[1000][1000], dis[2050], num;
char word[10][100];
char s[2050];
int len[10];
void DP() {
memset(dis, 127, sizeof(dis));
for (int i = 1; i <= n; i++)
for (int j = 1; j <= num; j++) {
if ((dis[i] <= (i + len[j] - 1)) || (i + len[j] - 1 > n))
continue;
bool flag = 0;
for (int k = 0; k < len[j]; k++)
if (s[i + k] != word[j][k + 1]) {
flag = 1;
break;
}
if (flag == 1)
continue;
dis[i] = min(dis[i], i + len[j] - 1);
}
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++) {
int w = 0;
for (int k = i; k >= j; k--) {
if (dis[k] <= i)
w++;
dp[i][j] = max(dp[i][j], dp[k - 1][j - 1] + w);
}
}
}
int main() {
scanf("%d%d", &p, &m);
for (int i = 1; i <= p; i++)
scanf("%s", s + 1 + 20 * (i - 1));
n = strlen(s + 1);
scanf("%d", &num);
for (int i = 1; i <= num; i++) {
scanf("%s", word[i] + 1);
len[i] = strlen(word[i] + 1);
}
DP();
printf("%d\n", dp[n][m]);
return 0;
}
```
**dalao勿喷，萌新别抄**
\
~~_最后，给个关注嘛！_~~
by Shenyufan13 @ 2024-08-18 22:19:42