美团codeM预赛A 合并回文子串

合并回文子串

时间限制：2秒

空间限制：262144K

输入两个字符串A和B，合并成一个串C，属于A和B的字符在C中顺序保持不变。如"abc"和"xyz"可以被组合成"axbycz"或"abxcyz"等。 我们定义字符串的价值为其最长回文子串的长度（回文串表示从正反两边看完全一致的字符串，如"aba"和"xyyx"）。 需要求出所有可能的C中价值最大的字符串，输出这个最大价值即可 

输入描述:

第一行一个整数T(T ≤ 50)。 接下来2T行，每两行两个字符串分别代表A,B(|A|,|B| ≤ 50)，A,B的字符集为全体小写字母。

输出描述:

对于每组数据输出一行一个整数表示价值最大的C的价值。

输入例子1:

2 aa bb a aaaabcaa

输出例子1:

4 5

解题思路；dp[i][j][k][l]表示s1[i,j]与s2[k,l]的合并后能否组成回文子串，可以匹配第一个字符和最后一个字符来转移，根据第一个字符和最后一个字符分别来自s1还是s2共有四种转移:(1)dp[i][j][k][l]<-dp[i+1][j-1][k][l],(2)dp[i][j][k][l]<-dp[i+1][j][k][l-1],(3)dp[i][j][k][l]<-dp[i][j-1][k+1][l],(4)dp[i][j][k][l]<-dp[i][j][k+1][l-1]

边界情况：当 j – i + 1 + l – k + 1 = 0 时答案是 true,当 j – i + 1 + l – k + 1 = 1 时答案是 true

#include <iostream> #include <cstdio> #include <cstring> #include <string> #include <algorithm> #include <queue> #include <stack> #include <cmath> #include <map> #include <bitset> #include <set> #include <vector> #include <functional> using namespace std; #define LL long long const int INF = 0x3f3f3f3f; char s1[60],s2[60]; bool dp[60][60][60][60]; int main() { int t; scanf("%d",&t); while(t--) { scanf("%s%s",s1+1,s2+1); int len1=strlen(s1+1),len2=strlen(s2+1); memset(dp,0,sizeof dp); int ans=0; for(int d1=0; d1<=len1; d1++) { for(int d2=0; d2<=len2; d2++) { for(int i=1,j=d1; j<=len1; i++,j++) { for(int k=1,l=d2; l<=len2; k++,l++) { if(d1+d2<=1) dp[i][j][k][l]=1; else { if(d1>1&&s1[i]==s1[j]) dp[i][j][k][l]|=dp[i+1][j-1][k][l]; if(d1&&d2&&s1[i]==s2[l]) dp[i][j][k][l]|=dp[i+1][j][k][l-1]; if(d1&&d2&&s2[k]==s1[j]) dp[i][j][k][l]|=dp[i][j-1][k+1][l]; if(d2>1&&s2[k]==s2[l]) dp[i][j][k][l]|=dp[i][j][k+1][l-1]; } if(dp[i][j][k][l]) ans=max(ans,d1+d2); } } } } printf("%d\n",ans); } return 0; }