pypy3 解法, 执行用时: 3791ms, 内存消耗: 226608K, 提交时间: 2021-05-22 22:46:22

T = int(input())
for _ in range(T):
	a, b = input().strip(), input().strip()
	n, m, ans = len(a), len(b), [0]
	dp = [[False] * (m + 1) * (m + 1) for _ in range((n + 1) * (n + 1))]

	def solve(i, j, k, l):
		if dp[i * (n + 1) + j][k * (m + 1) + l]: return
		ans[0] = max(ans[0], j - i + l - k)
		dp[i * (n + 1) + j][k * (m + 1) + l] = True
		if j + 1 <= n:
			if i > 0 and a[i - 1] == a[j]: solve(i - 1, j + 1, k, l)
			if k > 0 and b[k - 1] == a[j]: solve(i, j + 1, k - 1, l)
		if l + 1 <= m:
			if k > 0 and b[k - 1] == b[l]: solve(i, j, k - 1, l + 1)
			if i > 0 and a[i - 1] == b[l]: solve(i - 1, j, k, l + 1)

	for j in range(n + 1):
		for l in range(m + 1):
			for i in range(j + 1):
				for k in range(l + 1):
					if j - i + l - k <= 1:
						solve(i, j, k, l)
	print(ans[0])

C++(g++ 7.5.0) 解法, 执行用时: 484ms, 内存消耗: 8136K, 提交时间: 2022-10-05 20:38:25

#include<bits/stdc++.h>
using namespace std;
char a[55],b[55];
bool f[53][53][53][53];
int main(){
	int T;
	cin>>T;
	while(T--){
		cin>>a+1>>b+1;
		memset(f,0,sizeof f);
		int la=strlen(a+1),lb=strlen(b+1),ans=1;
		for(int i=la+1;i>0;--i)
			for(int k=lb+1;k>0;--k)
				for(int j=i-1;j<=la;++j)
					for(int l=k-1;l<=lb;++l){
						int len_a=j-i+1,len_b=l-k+1;
						if(len_a+len_b<=1){
							f[i][j][k][l]=1;
							continue;
						}
						if(len_a>1&&a[i]==a[j])
							f[i][j][k][l]|=f[i+1][j-1][k][l];
						if(len_b>1&&b[k]==b[l])
							f[i][j][k][l]|=f[i][j][k+1][l-1];
						f[i][j][k][l]|=f[i][j-1][k+1][l]&(a[j]==b[k]);
						f[i][j][k][l]|=f[i+1][j][k][l-1]&(a[i]==b[l]);
						if(f[i][j][k][l])
							ans=max(ans,len_a+len_b);
					}
		cout<<ans<<endl;
	}
	return 0;
}

C++(clang++ 11.0.1) 解法, 执行用时: 677ms, 内存消耗: 4636K, 提交时间: 2022-07-30 11:53:33

#include<bits/stdc++.h>
using namespace std;
const int N=55;
bool dp[N][N][N][N];
int main (void)
{
	int t;
	cin>>t;
	while(t--)
	{
		string a,b;
		cin>>a>>b;
		int ans=0;
		for(int l1=0;l1<=a.size();l1++)
		for(int l2=0;l2<=b.size();l2++)
		for(int i=1;i+l1-1<=a.size();i++)
		for(int j=1;j+l2-1<=b.size();j++)
		{
			bool f=0;
			if(l1+l2<=1) f=1;
			if(i+l1-2>=0&&a[i-1]==a[i+l1-2]&&dp[i+1][i+l1-2][j][j+l2-1]) f=1;
			if(j+l2-2>=0&&b[j-1]==b[j+l2-2]&&dp[i][i+l1-1][j+1][j+l2-2]) f=1;
			if(j+l2-2>=0&&a[i-1]==b[j+l2-2]&&dp[i+1][i+l1-1][j][j+l2-2]) f=1;
			if(i+l2-2>=0&&b[j-1]==a[i+l1-2]&&dp[i][i+l1-2][j+1][j+l2-1]) f=1;
			dp[i][i+l1-1][j][j+l2-1]=f;
			if(f) ans=max(ans,l1+l2);
		}
		cout<<ans<<endl;
	}
}