一看完这道题就知道是划分型dp
有两个点要注意
（1）怎么预处理子串。
表示以i为开头，结尾在j之前（含），有没有子串，有就1，没有就0
（2）dp的过程
这种分成k组最优的题目已经高度模板化了，我总结一下吧
//f[i][j]表示把前j个数分成i组的最优价值
memset(f, 0xc0, sizeof(f)); //初始化
f[0][0] = 0; //不要忘记了
_for(k, 1, K) //枚举组数 _for(i, 1, len) //前i个字符 _for(j, 1, i) //断点 f[k][i] = max(f[k][i], f[k-1][j-1] + sum[j][i]); //字母不要写错
printf("%d\n", f[K][len]);
最后用string可以很方便的连接字符串，直接+=
char的话用strcat, stract(a, b)表示把b连到a后面
#include<cstdio>
#include<string>
#include<cstring>
#include<algorithm>
#include<iostream>
#define REP(i, a, b) for(int i = (a); i < (b); i++)
#define _for(i, a, b) for(int i = (a); i <= (b); i++)
using namespace std;const int MAXN = 212;
string s, t, word[10];
int p, K, n, sum[MAXN][MAXN], f[MAXN][MAXN];bool judge(int i, int j)
{REP(r, 0, n){int len = word[r].length();if(len > (j - i + 1)) continue;REP(k, 0, len){if(word[r][k] != s[i+k]) break;if(k == len - 1) return true;} }return false;
}int main()
{while(~scanf("%d%d", &p, &K)){s = "0";REP(i, 0, p){cin >> t;s += t;}p *= 20;scanf("%d", &n);REP(i, 0, n) cin >> word[i];memset(sum, 0, sizeof(sum));_for(j, 1, p)for(int i = j; i >= 1; i--)sum[i][j] = sum[i+1][j] + judge(i, j);memset(f, 0xc0, sizeof(f));f[0][0] = 0;_for(k, 1, K)_for(i, 1, p)_for(r, 1, i)f[k][i] = max(f[k][i], f[k-1][r-1] + sum[j][i]);printf("%d\n", f[K][p]);}return 0;
}