[区间dp] NC13230合并回文子串

题面

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

分析

  若是这题暴力把所有合成的 C 串找出来，则共有 $C_{100}^{50}$ 种可能，这种指数复杂度是不能承受的。而类比找一个字符串的回文串，若是只是单个字符串，我们可以通过dp进行 $O(n^2)$ 的算法：

//字符串从s[1]开始存储，长度为len for(int L = 1; L <= len; L++) { for(int i = 1; i + L - 1 <= len; i++) { int j = i + L - 1; if(s[i] == s[j] && (L <= 2 || dp[i+1][j-1])) { dp[i][j] = 1; ans = max(ans, L); } } }

  若是要用动态规划，区间dp的思想是考虑从小规模的状态转移到大规模的状态，因此肯定是从长度较小的回文子串转移到长度较大的回文子串，即如果一个回文串首尾加上同样的字母，可以构成一个新的更长的回文串。   若是用 $dp[i][j]$ 表示区间 $[i,j]$ 构成的子串是不是回文串(01表示)，那么一个区间是回文串有以下三种可能：   ①$i=j$，即单个字符是回文串；   ②$i=j-1$ 并且 $s[i]=s[j]$，即两个一样的字符是回文串；   ③ $i<j-1$ 并且 $s[i]=s[j]，dp[i+1][j-1]=1$，即一个回文串首尾加上同样的字母，可以构成一个新的更长的回文串。   因此若是求单个字符串的回文子串，大循环是区间长度，小循环是区间起始位置进行双重循环就行，当然还有更优秀的马拉车算法($O(n)$) 。      对于这一题，我们需要考虑的是两个字符串组合得到的回文串，则需要四维 $dp[i][k][j][l]$, 表示 $A[i][k],B[j][l]$ 是否可以组成一个回文串。记 $le{n}_1=k-i+1，le{n}_2=l-j+1$， 同样地，我们需要考虑状态转移：   ①如果 $le{n}_1+le{n}_2\le 1$, 则 $dp[i][k][j][l]$ 为 1。等于 1 时两个字符串的截取一个为空，一个长度为1，自然是回文串；等于 0 时两个字符串都截取为空，其实是没有回文串的定义的，但是为了之后的转移方便(如从 $dp[0][0][0][0]$ 转移到 $dp[1][1][1][1]$), 定义为1。   ②如果 $le{n}_1>1$, 那么对于 $dp[i][k][j][l]$, 若 $A[i]=A[k]$ 且 $dp[i+1][k-1][j][l]=1$，那么首尾加上 $A[i]，A[k]$还是回文串，则$dp[i][k][j][l]=1$ 。同理对于$le{n}_2>1$。   ③如果$le{n}_1>0$ 且 $le{n}_2>0$, 若$A[i]=B[l]$ 且 $dp[i+1][k][j][l-1]=1$， 那么在首尾加上 $A[i],B[l]$ 还是回文串，则$dp[i][k][j][l]=1$ 。同理对于$A[k]=B[j]$ 且 $dp[i][k-1][j+1][l]=1$。      所以以上就得出了从小回文串转移到大回文串的区间动态规划过程。通过四重循环，前两重为A, B串截取的长度，后两重为 A, B串的区间起始位置，在计算时记录最大值就可以解决了。   

代码

#include <bits/stdc++.h> using namespace std; typedef unsigned long long ll; const int maxn = 1005; const int INF = 0x3f3f3f3f; const ll mod = 998244353; char a[52], b[52]; int f[52][52][52][52], len1, len2, ans; int main() { int t; scanf("%d", &t); while(t--) { ans = 1; scanf("%s %s", a + 1, b + 1); len1 = strlen(a + 1), len2 = strlen(b + 1); for(int k1 = 0; k1 <= len1; k1++) //前两重循环区间长度 for(int k2 = 0; k2 <= len2; k2++) for(int i = 1; i + k1 - 1 <= len1; i++) //后两重循环区间起始位置 for(int j = 1; j + k2 - 1 <= len2; j++) { int k = i + k1 - 1, l = j + k2 - 1; if(k1 + k2 <= 1) //根据状态转移方程得出 f[i][k][j][l] = 1; else { f[i][k][j][l] = 0; //由于有多次询问，因此需要清零防止上次的dp数据干扰 if(k1 > 1) f[i][k][j][l] |= (f[i+1][k-1][j][l] && a[i] == a[k]); if(k2 > 1) f[i][k][j][l] |= (f[i][k][j+1][l-1] && b[j] == b[l]); if(k1 && k2) f[i][k][j][l] |= (f[i+1][k][j][l-1] && a[i] == b[l]); if(k1 && k2) f[i][k][j][l] |= (f[i][k-1][j+1][l] && a[k] == b[j]); } if(f[i][k][j][l]) ans = max(ans, k1 + k2); } printf("%d\n", ans); } }

  除了转移方程，还需要特别注意动态规划过程边界的处理。