题意
输入两个字符串A和B,合并成一个串C,属于A和B的字符在C中顺序保持不变。如"abc"和"xyz"可以被组合成"axbycz"或"abxcyz"等。
我们定义字符串的价值为其最长回文子串的长度(回文串表示从正反两边看完全一致的字符串,如"aba"和"xyyx")。
需要求出所有可能的C中价值最大的字符串,输出这个最大价值即可
题解
遇到这种数据范围较小的计数问题应该优先考虑dp,本题就是如此。
那么应该怎么样考虑转移呢?
首先最后C中的那个价值最大的子串一定是由字符串A的一个区间和字符串B的一个区间合并得到的,
那么现在假设A[i] ~ A[j]与B[k] ~ B[l]构成了一个回文串(这里设dp[i][j][k][l])
则他能转移到的区间有
1:a[i-1]==a[j+1]时 dp[i-1][j+1][k][l]
2:a[i-1]==b[l+1]时 dp[i-1][j][k][l+1]
3:b[k-1]==a[j+1]时 dp[i][j+1][k-1][l]
4:b[k-1]==b[l+1]时 dp[i][j][k-1][l+1]
那么对应的转移方程就为
if(a[i]==a[j]) dp[i][j][k][l]|=dp[i+1][j-1][k][l]; if(a[i]==b[l]) dp[i][j][k][l]|=dp[i+1][j][k][l-1]; if(b[k]==b[l]) dp[i][j][k][l]|=dp[i][j][k+1][l-1]; if(b[k]==a[j]) dp[i][j][k][l]|=dp[i][j-1][k+1][l];
然后就可以轻松的区间转移啦~
oh,在注意一下枚举过程中只有一个字母的状态一定是回文的就可以啦
代码
#include<bits/stdc++.h> #define pb push_back #define fi first #define se second using namespace std; typedef long long LL; typedef unsigned long long uLL; typedef pair<int,int> PII; typedef pair<LL,LL> PLL; typedef vector<int> VI; const int N = 5e3+5; const int mod =1e9+7; const LL inf = 0x3f3f3f3f3f3f3f3f; const int maxn = 2e6+6; int _,ans,la,lb,dp[55][55][55][55]; char a[maxn],b[maxn]; int main(){ for(scanf("%d",&_);_;_--){ scanf("%s",a+1); scanf("%s",b+1); la=strlen(a+1);lb=strlen(b+1); ans=0; for(int l1=0;l1<=la;l1++){ for(int l2=0;l2<=lb;l2++){ for(int i=1;i<=la-l1+1;i++){ for(int k=1;k<=lb-l2+1;k++){ int j=i+l1-1,l=k+l2-1; if(l1+l2<=1) dp[i][j][k][l]=1; else { dp[i][j][k][l]=0; if(a[i]==a[j]) dp[i][j][k][l]|=dp[i+1][j-1][k][l]; if(b[k]==b[l]) dp[i][j][k][l]|=dp[i][j][k+1][l-1]; if(a[i]==b[l]) dp[i][j][k][l]|=dp[i+1][j][k][l-1]; if(b[k]==a[j]) dp[i][j][k][l]|=dp[i][j-1][k+1][l]; } if(dp[i][j][k][l]) ans=max(ans,l1+l2); } } } } printf("%d\n",ans); } }