【每日一题】合并回文子串、区间DP
输入两个字符串A和B，合并成一个串C，属于A和B的字符在C中顺序保持不变。如"abc"和"xyz"可以被组合成"axbycz"或"abxcyz"等。
我们定义字符串的价值为其最长回文子串的长度（回文串表示从正反两边看完全一致的字符串，如"aba"和"xyyx"）。
需要求出所有可能的C中价值最大的字符串，输出这个最大价值即可
我们定义字符串的价值为其最长回文子串的长度（回文串表示从正反两边看完全一致的字符串，如"aba"和"xyyx"）。
需要求出所有可能的C中价值最大的字符串，输出这个最大价值即可
————————————————————————————————
被虐了=='
平时做过二维区间dp，石头合并经典题，写过区间dp的板子
所以知道实现的时候肯定是四个for循环。枚举所有的ijkl；
basecase是：当只选出一个字符，肯定是回文
【心得】
区间DP不咋熟，看来得练习区间DP，多写写就知道套路了
状态的表示不是直接表示为最长长度，而是表示为能否构成回文（bool）,然后看所有能构成的里面的最长长度====
写代码的时候注意一点：因为i-1 j-1这种涉及到-1下标，比较简单的处理是让字符串的下标从1开始
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int maxn = 1e5 + 10;
#define MAXN 55
int main(void)
{
int T;cin>>T;
int dp[MAXN][MAXN][MAXN][MAXN];//状态：s1中选i~j,s2中选k~l是否可以构成回文串
while(T--){
char s1[maxn],s2[maxn];
scanf("%s",s1+1);scanf("%s",s2+1);
memset(dp,0,sizeof(dp));
int ans=0;
int len1=strlen(s1+1);int len2=strlen(s2+1);
for(int gap1=0;gap1<=len1;++gap1){
for(int gap2=0;gap2<=len2;++gap2)
for(int i=1;i<=len1-gap1+1;++i)
for(int k=1;k<=len2-gap2+1;++k){
int j=i+gap1-1;int l=k+gap2-1;
if(gap1+gap2<=1) {
dp[i][j][k][l]=1;
ans=max(ans,gap1+gap2);
continue;
}
if(s1[i]==s1[j]) dp[i][j][k][l] |= dp[i+1][j-1][k][l];
if(s2[k]==s2[l]) dp[i][j][k][l] |= dp[i][j][k+1][l-1];
if(s1[i]==s2[l]) dp[i][j][k][l] |= dp[i+1][j][k][l-1];
if(s1[j]==s2[k]) dp[i][j][k][l] |= dp[i][j-1][k+1][l];
if(dp[i][j][k][l]) ans=max(ans,gap1+gap2);
}
}
cout << ans << endl;
}
return 0;
}
拼多多集团-PDD公司福利 470人发布
投递中国农业发展银行等公司10个岗位 >