本题在洛谷上的链接：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 
      
        2 #include 
       
         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 }