【每日一题】3-25 合并回文子串

题目链接：

https://ac.nowcoder.com/acm/problem/13230

题意：

给你两个字符串，把他们拼成一个字符串，并且A，B字符串中字符的的相对位置不变

定义字符串的价值为他的最长回文子串的长度，求拼成的字符串的最大价值

题解：

考虑区间 dp，这里我们假设第一个字符串是 $s1$ ，第二个字符串是 $s2$

设 $dp[st1][ed1][st2][ed2]$ 表示取第一个字符串的 $[st1,ed1]$ 和第二个字符串的 $[st2,ed2]$ 能否构成回文串。

并且这个状态是可以转移的，如果第一个字符串的 $[st1,ed1]$ 和第二个字符串的 $[st2,ed2]$ 能否构成回文串的话。

我们把 $s1[st1-1]$ 或者 $s2[st2-1]$ 加在前面，并且把 $s1[ed1+1]$ 或者 $s2[ed2+1]$ 加在后面，构成另一个状态。

然后我们就可以考虑状态转移了，如果 $dp[st1][ed1][st2][ed2]$ 是回文串

并且可以通过上述 4 种方式在它的首尾加上一个字母还是回文串，那么下一个状态也是回文串，所以我们可以得到状态转移的关键步骤

if (dp[st1][ed1][st2][ed2])
{
	if (s1[st1 - 1] == s1[ed1 + 1])
		dp[st1 - 1][ed1 + 1][st2][ed2] = true;
	if (s1[st1 - 1] == s2[ed2 + 1])
		dp[st1 - 1][ed1][st2][ed2 + 1] = true;
	if (s1[ed1 + 1] == s2[st2 - 1])
		dp[st1][ed1 + 1][st2 - 1][ed2] = true;
	if (s2[st2 - 1] == s2[ed2 + 1])
		dp[st1][ed1][st2 - 1][ed2 + 1] = true;
}

然后我们会发现在这里我们似乎不能表示不取的状态，但我们可以用 $[i,i-1]$ 这种状态来表示不取的状态。

然后处理处理边界，所有长度小于等于 1 的状态都是回文串

for (int i = 0; i <= len1 + 1; i++)
{
	for (int j = 0; j <= len2 + 1; j++)
	{
		if (j)
			dp[i][i][j][j - 1] = true;
		if (i)
			dp[i][i - 1][j][j] = true;
		if (i && j)
			dp[i][i - 1][j][j - 1] = true;
	}
}

别忘了初始化，最好只初始化一组数据可能用到的部分就可以了

for (int i = 0; i <= len1 + 1; i++)
	for (int j = 0; j <= len1 + 1; j++)
		for (int k = 0; k <= len2 + 1; k++)
			for (int l = 0; l <= len2 + 1; l++)
				dp[i][j][k][l] = false;

代码：

#include <bits/stdc++.h>
#define ll long long
#define sc scanf
#define pr printf
using namespace std;
const int MAXN = 55;
bool dp[MAXN][MAXN][MAXN][MAXN];
char s1[MAXN], s2[MAXN];
int main()
{
	int T;
	sc("%d", &T);
	while (T--)
	{
		sc("%s%s", s1 + 1, s2 + 1);
		int len1 = strlen(s1 + 1), len2 = strlen(s2 + 1);
		for (int i = 0; i <= len1 + 1; i++)
			for (int j = 0; j <= len1 + 1; j++)
				for (int k = 0; k <= len2 + 1; k++)
					for (int l = 0; l <= len2 + 1; l++)
						dp[i][j][k][l] = false;
		for (int i = 0; i <= len1 + 1; i++)
		{
			for (int j = 0; j <= len2 + 1; j++)
			{
				if (j)
					dp[i][i][j][j - 1] = true;
				if (i)
					dp[i][i - 1][j][j] = true;
				if (i && j)
					dp[i][i - 1][j][j - 1] = true;
			}
		}
		int ans = 1;
		for (int i = 0; i <= len1; i++)
		{
			for (int j = 0; j <= len2; j++)
			{
				for (int st1 = 1, ed1 = st1 + i - 1; ed1 <= len1; st1++, ed1++)
				{
					for (int st2 = 1, ed2 = st2 + j - 1; ed2 <= len2; st2++, ed2++)
					{
						if (dp[st1][ed1][st2][ed2])
						{
							ans = max(ans, ed1 - st1 + 1 + ed2 - st2 + 1);
							if (s1[st1 - 1] == s1[ed1 + 1])
								dp[st1 - 1][ed1 + 1][st2][ed2] = true;
							if (s1[st1 - 1] == s2[ed2 + 1])
								dp[st1 - 1][ed1][st2][ed2 + 1] = true;
							if (s1[ed1 + 1] == s2[st2 - 1])
								dp[st1][ed1 + 1][st2 - 1][ed2] = true;
							if (s2[st2 - 1] == s2[ed2 + 1])
								dp[st1][ed1][st2 - 1][ed2 + 1] = true;
						}
					}
				}
			}
		}
		pr("%d\n", ans);
	}
}