刷题记录:牛客NC13230合并回文子串

传送门:牛客

题目描述:

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

感觉这道区间dp题巨难(对于我这种只会简单的二维区间dp选手来说),所以为什么难度才三星,不过写完之后感觉感悟巨大就是了??

主要思路:

1. 我们可以使用$dp[i][j][k][l]$来记录$a串中i到j位置的子串和b串中k到l位置的子串能否合并为一个回文串$,注意这里记录的能不能成为一个回文串,而不是回文串的最大价值,因为假设我们记录的是回文串的最大价值那么我们将无法进行转移
2. 那么对于我们的$dp[i][j][k][l]$,我们有大致四个决策,
3. 假设我们的$a[i]==a[j]$,那么显然的我们可以将我们的问题变成$dp[i+1][j-1][k][l]$能不能成为一个回文串,因为我们此时可以将我们的a串的两端放在我们的合并串的两端;
4. 同理若$a[i]==b[l]$,我们只需要判断$dp[i+1][j][k][l-1]$即可
5. 同理若$a[j]==b[k]$,我们只需要判断$dp[i][j-1][k+1][l]$即可
6. 同理若$b[k]==b[l]$,我们只需要判断$dp[i][j][k+1][l-1]$即可
7. 想明白上面的转移过程之后,我们还有一个比较麻烦的事情要做,那就是我们还需要完成边界问题.仔细观察上面的转移方程,我们可能出现右端点小于左端点的情况,此时我们需要将其赋值为1,不然会导致错误.幸好这种问题可以被巧妙的解决,我们只需要将我们的长度为0也加入我们的区间dp的循环之中即可(这道题的区间dp是需要枚举两个子串的长度和各自的端点).我感觉这个长度为0是最妙的,甚至超过了前面推dp方程的难度,并且当我们的合并子串的长度为1时,显然也是一个回文字符串,所以此时我门也需要将其赋值为1.总结一下就是当合并子串的长度$<=1$时,需要将我们的dp数组赋值为1

下面是具体的代码部分:

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
typedef long long ll;
#define inf 0x3f3f3f3f
#define root 1,n,1
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
inline ll read() {
	ll x=0,w=1;char ch=getchar();
	for(;ch>'9'||ch<'0';ch=getchar()) if(ch=='-') w=-1;
	for(;ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0';
	return x*w;
}
#define maxn 1000000
#define ll_maxn 0x3f3f3f3f3f3f3f3f
const double eps=1e-8;
int T;
char a[100],b[100];
bool dp[100][100][100][100];
int main() {
	T=read();
	while(T--) {
		scanf("%s%s",a+1,b+1);
		int lena=strlen(a+1),lenb=strlen(b+1);
		int ans=-inf;
		for(int n=0;n<=lena;n++) {
			for(int m=0;m<=lenb;m++) {
				for(int i=1;i<=lena-n+1;i++) {
					for(int k=1;k<=lenb-m+1;k++) {
						int j=i+n-1,l=k+m-1;
						if(n+m<=1) dp[i][j][k][l]=1;
						//长度为0代表不合法的情况,规定为1,巧妙地解决边界问题
						//长度为1代表一个字符,显然是回文串
						else {
							dp[i][j][k][l]=0;
							if(n>1) dp[i][j][k][l]|=(dp[i+1][j-1][k][l])&&(a[i]==a[j]);
							if(n&&m) dp[i][j][k][l]|=(dp[i+1][j][k][l-1])&&(a[i]==b[l]);//注意此时只需要加起来的长度大于等于2即可,不需要满足各自大于等于2
							if(n&&m) dp[i][j][k][l]|=(dp[i][j-1][k+1][l])&&(a[j]==b[k]);
							if(m>1) dp[i][j][k][l]|=(dp[i][j][k+1][l-1])&&(b[k]==b[l]);
						}
						if(dp[i][j][k][l]) {
							ans=max(ans,n+m);
						}
					}
				}
			}
		}
		cout<<ans<<endl;
	}
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61