原题链接：更好的阅读体验
题目描述
输入两个字符串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
输出
复制
4
5
思路：
以前做过判断一个字符串的：传送门
当时是用的二维dp。
令dp[i][j]表示S[i]至S[j]所表示的子串是否是回文子串，是则为1，不是为0。这样根据S[i]是否等于S[j]，可以把转移情况分为两类：
①若S[i]=S[j],那么只要S[i+1]和S[j-1]是回文子串，S[i]至S[j-1]就是回文子串；如果S[i+1]至S[j-1]不是回文子串，则S[i]至S[j]一定不是回文子串。
②若S[i]!=S[j]，那S[i]至S[j]一定不是回文子串。
————————————————
版权声明：本文为CSDN博主「qq_42265608」的原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/qq_42265608/article/details/89514122
现在的两个字符串可以考虑下用四维dp来维护，数据范围也足够友好。
状态转移的话跟一维的类似：
dp[sa][ea][sb][eb]=0; if(a[sa]==a[ea]) dp[sa][ea][sb][eb]|=dp[sa+1][ea-1][sb][eb]; if(b[sb]==b[eb]) dp[sa][ea][sb][eb]|=dp[sa][ea][sb+1][eb-1]; if(a[sa]==b[eb]) dp[sa][ea][sb][eb]|=dp[sa+1][ea][sb][eb-1]; if(a[ea]==b[sb]) dp[sa][ea][sb][eb]|=dp[sa][ea-1][sb+1][eb];
代码：
真·繁琐
#include<bits/stdc++.h> using namespace std; const int maxn=55; bool dp[maxn][maxn][maxn][maxn]; ///dp[i][j][k][q]表示a的i~j和b的k~q可以够成回文子串的最大长度 char a[maxn],b[maxn]; int main(){ int t;cin>>t; while(t--){ cin>>a+1>>b+1; int maxx=-0x3f3f3f3f; int lena=strlen(a+1),lenb=strlen(b+1); for(int la=0;la<=lena;la++)///枚举a长度 for(int lb=0;lb<=lenb;lb++)///枚举b长度 for(int sa=1;sa+la-1<=lena;sa++)///枚举a起点 for(int sb=1;sb+lb-1<=lenb;sb++){///枚举b起点 int ea=sa+la-1,eb=sb+lb-1; // bool &x=dp[sa][ea][sb][eb]; if(la+lb<=1) dp[sa][ea][sb][eb]=1; else{ dp[sa][ea][sb][eb]=0; if(a[sa]==a[ea]) dp[sa][ea][sb][eb]|=dp[sa+1][ea-1][sb][eb]; if(b[sb]==b[eb]) dp[sa][ea][sb][eb]|=dp[sa][ea][sb+1][eb-1]; if(a[sa]==b[eb]) dp[sa][ea][sb][eb]|=dp[sa+1][ea][sb][eb-1]; if(a[ea]==b[sb]) dp[sa][ea][sb][eb]|=dp[sa][ea-1][sb+1][eb]; } if(dp[sa][ea][sb][eb]) maxx=max(maxx,la+lb); } printf("%d\n",maxx); } return 0; }
