题目大意
两个字符串strA和strB(长度最大为2100)，他们中按照顺序有一些公共的子串，且公共子串的长度大于等于3，否则不认为是合法的，比如 abcdef 和 abcxcdef, 按照顺序有合法公共子串abc def 或者 cdef。
按照顺序取出一些公共子串，有不同的取法，求这些取法中公共子串长度之和的最大值。
题目分析
字符串长度最大为2100，因此直接枚举搜索会超时，考虑使用动态规划，且复杂度要降到 O(n^3) 甚至 O(n^2). 用状态 dp[i][j][0] 表示strA 前i个字符和strB 前j个字符中满足合法条件的公共子串的长度之和； dp[i][j][1] 表示strA 前i个字符和strB 前j个字符的公共后缀的长度。
状态 dp[i][j][1] 很好找到状态转移方程，而对于 dp[i][j][0]：
（1）如果 strA[i-1] == strB[j-1]，可以根据 dp[i][j][1] 来看，如果 dp[i][j][1] 大于等于3，即为len，则dp[i][j][0]可以根据 dp[i-k][j-k][0]来进行更新(其中k >= 3, k <= len)。因为 在选择最后一个子串的时候，可以选择长度为3,4...len。
（2）如果 strA[i-1] != strB[j-1]，则 dp[i][j][0] = max{dp[i][j-1][0], dp[i-1][j][0]}
实现
#include<iostream>
#include<stdio.h>
#include<string.h>
#include<stack>
#include<vector>
#include<unordered_set>
#include<unordered_map>
using namespace std; int dp[2200][2200][2];
//dp[i][j][0] 表示 strA 前i个字符和strB前j个字符中满足条件的公共子串的长度之和
//dp[i][j][1] 表示 strA 前i个字符和strB前j个字符的公共后缀的长度
char strA[2200];
char strB[2200];
int max(int a, int b){
return a > b ? a : b;
}
int main(){
scanf("%s", strA);
scanf("%s", strB);
int m = strlen(strA);
int n = strlen(strB);
memset(dp, 0, sizeof(dp)); for (int i = 1; i <= m; i++){
for (int j = 1; j <= n; j++){
dp[i][j][0] = max(dp[i - 1][j][0], dp[i][j - 1][0]);
if (strA[i - 1] == strB[j - 1]){
dp[i][j][1] = dp[i - 1][j - 1][1] + 1;
if (dp[i][j][1] >= 3){
dp[i][j][0] = max(dp[i][j][0], dp[i - 3][j - 3][0] + 3);
dp[i][j][0] = max(dp[i][j][0], dp[i - dp[i][j][1]][j - dp[i][j][1]][0] + dp[i][j][1]);
}
/*
if (dp[i][j][1] >= 3){ //当以 strA以i结尾，strB 以j结尾的后缀长度dp[i][j][1]大于等于3，则需要进行状态更新
//不能直接 dp[i][j][0] = max(dp[i][j][0], dp[i - dp[i][j][1]][j - dp[i][j][1]][0] + dp[i][j][1]);
//这样有可能不是最优解，例如 abcdef, abcxcdef. 最后的 dp[i][j][1] = 4， 如果计算dp[6][7][0]的时候使用dp[i][j][1] = 4
//进行状态转移，那么只计算 dp[6][7][0] = max(dp[6][7][0], dp[2][3][0] + 4) 而dp[2][3][0] = 0,
//而此时的最优结果为 dp[3][4][0] + 3 (dp[i][j][1] 中只取后面的一部分就够了）
for (int k = 3; k <= dp[i][j][1]; k ++)
dp[i][j][0] = max(dp[i][j][0], dp[i - k][j - k][0] + k);
}
*/
}
}
}
printf("%d\n", dp[m][n][0]);
return 0;
}