本题在洛谷上的链接：https://www.luogu.org/problemnew/show/P1026
比较考验动规技巧及代码能力的一道题。题目描述的并不算太清晰，简单解释一下，就是说，把一个字符串划成k份，对于每一份单独统计里面出现的单词的个数，注意，对于同一个字母，最多匹配到一个单词，然后把统计的个数相加，现在想让这个和最多，问你最大值是多少。
设dp[i][j]为将[1,i]划分成j份的单词数之和的最大值。那么dp[i][j]=max(dp[i][j],dp[p][j-1]+cnt[p+1][i])。其中cnt[p+1][j]表示[p+1,j]中能匹配到多少个单词。
一开始我们需要先预处理出cnt来，先简单匹配一下，KMP或暴力都行，然后用cnt[i][j]=cnt[i][j-1]+cnt[i+1][j]-cnt[i+1][j-1]枚举区间长度推出所有的cnt。然后预处理一下dp[i][1]=cnt[1][i]，再跑DP就可以了。
1 #include <cstdio> 2 #include <algorithm> 3 4 using namespace std; 5 6 int cnt[205][205], dp[205][45]; 7 char s[205], w[10][25]; 8 9 int main() { 10 int p, k, wc, n; 11 char c; 12 scanf("%d%d", &p, &k); 13 for (int i = 1; i <= p; ++i) 14 for (int j = 1; j <= 20; ++j) { 15 while ((c = getchar()) == ‘\n‘ || c == ‘ ‘ || c == ‘\r‘); 16 s[20 * (i - 1) + j] = c; 17 } 18 scanf("%d", &wc); 19 for (int i = 1; i <= wc; ++i) 20 scanf("%s", w[i] + 1); 21 n = 20 * p; 22 for (int i = 1; i <= n; ++i) 23 for (int j = 1; j <= wc; ++j) 24 for (int k = 1; w[j][k]; ++k) { 25 if (s[i + k - 1] != w[j][k]) break; 26 if (!w[j][k + 1]) cnt[i][i + k - 1] = 1; 27 } 28 for (int l = 1; l <= n; ++l) 29 for (int i = 1; i <= n - l + 1; ++i) { 30 int j = i + l - 1; 31 cnt[i][j] += cnt[i][j - 1] + cnt[i + 1][j] - cnt[i + 1][j - 1]; 32 } 33 for (int i = 1; i <= n; ++i) dp[i][1] = cnt[1][i]; 34 for (int j = 2; j <= k; ++j) 35 for (int i = 1; i <= n; ++i) 36 for (int p = j - 1; p < i; ++p) 37 dp[i][j] = max(dp[i][j], dp[p][j - 1] + cnt[p + 1][i]); 38 printf("%d", dp[n][k]); 39 return 0; 40 }
原文：https://www.cnblogs.com/Mr94Kevin/p/9801777.html
