题目链接:传送门
题目大意:给你两个长度均小于等于1000的字符串，你要在第一个串中找k个连续的子串，并且这些字串在第二个字符串中均出现且顺序相同，问这些字串最大的长度和。
题目思路:自己不会做，参考了大神的思路。
这个题相当于是最长公共子序列的拓展，我们用一个四维数组来转移状态，一二维表示比较第一个字符串的第i位和第二个字符串的第j位，第三维表示已经分配到
了第K段，第四维0表示当前第K段还会继续延伸，1表示不再延伸，然后转移状态即可。
#include <iostream> #include <cstdio> #include <cstdlib> #include <cmath> #include <algorithm> #include <cstring> #include <stack> #include <cctype> #include <queue> #include <string> #include <vector> #include <set> #include <map> #include <climits> #define lson root<<1,l,mid #define rson root<<1|1,mid+1,r #define fi first #define se second #define ping(x,y) ((x-y)*(x-y)) #define mst(x,y) memset(x,y,sizeof(x)) #define mcp(x,y) memcpy(x,y,sizeof(y)) using namespace std; #define gamma 0.5772156649015328606065120 #define MOD 1000000007 #define inf 0x3f3f3f3f #define N 100005 #define maxn 1005 typedef pair<int,int> PII; typedef long long LL; char str1[N],str2[N]; int dp[maxn][maxn][11][2]; int n,m,k; int main(){ int i,j,group,x,v; scanf("%d%d%d",&n,&m,&k); scanf("%s%s",str1+1,str2+1); for(i=1;i<=n;++i) for(j=1;j<=m;++j){ if(str1[i]==str2[j]) for(int l=1;l<=k;++l){ dp[i][j][l][0]=max(dp[i-1][j-1][l][0],dp[i-1][j-1][l-1][1])+1; } for(int l=1;l<=k;++l){ dp[i][j][l][1]=max({dp[i-1][j-1][l][1],dp[i-1][j][l][1],dp[i][j-1][l][1],dp[i][j][l][0]}); } } printf("%d ",dp[n][m][k][1]); return 0; }