DP52. 合并回文子串
描述
输入两个字符串A和B，合并成一个串C，属于A和B的字符在C中顺序保持不变。如"abc"和"xyz"可以被组合成"axbycz"或"abxcyz"等。输入描述
第一行一个整数T(T ≤ 50)。 接下来2T行，每两行两个字符串分别代表A,B(|A|,|B| ≤ 50)，A,B的字符集为全体小写字母。输出描述
对于每组数据输出一行一个整数表示价值最大的C的价值。示例1
输入:
2 aa bb a aaaabcaa
输出:
4 5
C++ 解法, 执行用时: 26ms, 内存消耗: 1564KB, 提交时间: 2021-10-22
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
ios::sync_with_stdio(false);
int T, nA, nB, res;
cin >> T;
string A, B;
ll f[52][52][52], gA[52], gB[52], t;
while (T--) {
cin >> A >> B;
nA = A.size(), nB = B.size();
for (int lA = 0; lA <= nA; ++lA)
for (int rA = 0; rA <= nA; ++rA)
for (int lB = 0; lB <= nB; ++lB)
f[lA][rA][lB] = rA - lA < 2 ? (1ll << lB | (lA == rA && lB < nB ? 1ll << lB + 1 : 0)) : 0;
for (int i = 1; i <= nA; ++i)
for (int j = gA[i] = 0; j <= nB - 1; ++j)
if (A[i - 1] == B[j]) gA[i] |= 1ll << j;
for (int i = 1; i <= nB; ++i)
for (int j = gB[i] = 0; j <= nB - 1; ++j)
if (B[i - 1] == B[j]) gB[i] |= 1ll << j;
res = 1;
for (int lA = nA; lA >= 0; --lA)
for (int rA = lA; rA <= nA; ++rA)
for (int lB = nB; lB >= 0; --lB)
if (t = f[lA][rA][lB]) {
if (lA) {
f[lA - 1][rA][lB] |= (t & gA[lA]) << 1;
if (A[lA - 1] == A[rA]) f[lA - 1][rA + 1][lB] |= t;
}
if (lB) {
f[lA][rA][lB - 1] |= (t & gB[lB]) << 1;
if (B[lB - 1] == A[rA]) f[lA][rA + 1][lB - 1] |= t;
}
res = max(res, rA - lA + 63 - __builtin_clzll(t) - lB);
}
cout << res << endl;
}
}
C++ 解法, 执行用时: 28ms, 内存消耗: 1568KB, 提交时间: 2022-05-08
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main() {
ios::sync_with_stdio(false);
int T, nA, nB, res;
cin >> T;
string A, B;
ll f[52][52][52], gA[52], gB[52], t;
while (T--) {
cin >> A >> B;
nA = A.size(), nB = B.size();
for (int lA = 0; lA <= nA; ++lA)
for (int rA = 0; rA <= nA; ++rA)
for (int lB = 0; lB <= nB; ++lB)
f[lA][rA][lB] = rA - lA < 2 ? (1ll << lB | (lA == rA &&
lB < nB ? 1ll << lB + 1 : 0)) : 0;
for (int i = 1; i <= nA; ++i)
for (int j = gA[i] = 0; j <= nB - 1; ++j)
if (A[i - 1] == B[j]) gA[i] |= 1ll << j;
for (int i = 1; i <= nB; ++i)
for (int j = gB[i] = 0; j <= nB - 1; ++j)
if (B[i - 1] == B[j]) gB[i] |= 1ll << j;
res = 1;
for (int lA = nA; lA >= 0; --lA)
for (int rA = lA; rA <= nA; ++rA)
for (int lB = nB; lB >= 0; --lB)
if (t = f[lA][rA][lB]) {
if (lA) {
f[lA - 1][rA][lB] |= (t & gA[lA]) << 1;
if (A[lA - 1] == A[rA]) f[lA - 1][rA + 1][lB] |= t;
}
if (lB) {
f[lA][rA][lB - 1] |= (t & gB[lB]) << 1;
if (B[lB - 1] == A[rA]) f[lA][rA + 1][lB - 1] |= t;
}
res = max(res, rA - lA + 63 - __builtin_clzll(t) - lB);
}
cout << res << endl;
}
}
C++ 解法, 执行用时: 28ms, 内存消耗: 3316KB, 提交时间: 2017-06-20
#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<string>
#include<algorithm>
#include<cmath>
#include<cstdio>
#include<set>
#include<map>
#include<queue>
#include<vector>
#include<cstring>
using namespace std;
char a[55], b[55];
char vis[55][55][55][55];
int la, lb;
int ans;
int cas;
void dfs(int abe, int aed, int bbe, int bed)
{
if (vis[abe][aed][bbe][bed] == cas)
{
return;
}
vis[abe][aed][bbe][bed] = cas;
ans = max(ans, aed - abe + bed - bbe);
if (abe > 0 && aed < la&&a[abe - 1] == a[aed])
{
dfs(abe - 1, aed + 1, bbe, bed);
}
if (bbe > 0 && bed < lb&&b[bbe - 1] == b[bed])
{
dfs(abe, aed, bbe - 1, bed + 1);
}
if (abe > 0 && bed < lb&&a[abe - 1] == b[bed])
{
dfs(abe - 1, aed, bbe, bed + 1);
}
if (bbe > 0 && aed < la&&b[bbe - 1] == a[aed])
{
dfs(abe, aed + 1, bbe - 1, bed);
}
return;
}
int main()
{
int t;
cin >> t;
while(t--)
{
cas++;
cin >> a >> b;
la = strlen(a);
lb = strlen(b);
ans = 0;
for (int i = 0;i <= la;i++)
{
for (int j = 0;j <= lb;j++)
{
dfs(i, i, j, j);
if (i != la)
{
dfs(i, i + 1, j, j);
}
if (j != lb)
{
dfs(i, i, j, j + 1);
}
}
}
cout << ans << "\n";
}
return 0;
}
C++ 解法, 执行用时: 34ms, 内存消耗: 1520KB, 提交时间: 2017-06-20
#include<cstdio>
#define F(a,b,c) for(int a=b;a<=c;a++)
#define R(a,b,c) for(int a=b;a>=c;a--)
typedef long long ll;
char A[52],B[52];
int nA,nB;
ll f[52][52][52],gA[52],gB[52];
void cmax(int&a,int b){b>a?a=b:1;}
int main(){
int T;scanf("%d",&T);
while(T--){
scanf("%s%s",A,B);
for(nA=0;A[nA];nA++);
for(nB=0;B[nB];nB++);
F(lA,0,nA)F(rA,0,nA)F(lB,0,nB)
f[lA][rA][lB]=rA-lA<2?1ll<<lB|(lA==rA&&lB<nB?1ll<<lB+1:0):0;
F(i,1,nA)F(j,gA[i]=0,nB-1)if(A[i-1]==B[j])gA[i]|=1ll<<j;
F(i,1,nB)F(j,gB[i]=0,nB-1)if(B[i-1]==B[j])gB[i]|=1ll<<j;
int ans=0;
ll s;
R(lA,nA,0)F(rA,lA,nA)R(lB,nB,0)if(s=f[lA][rA][lB]){
if(lA&&A[lA-1]==A[rA])f[lA-1][rA+1][lB]|=s;
if(lB&&B[lB-1]==A[rA])f[lA][rA+1][lB-1]|=s;
if(lA)f[lA-1][rA][lB]|=(s&gA[lA])<<1;
if(lB)f[lA][rA][lB-1]|=(s&gB[lB])<<1;
cmax(ans,rA-lA+63-__builtin_clzll(s)-lB);
}
printf("%d\n",ans);
}
}
C++ 解法, 执行用时: 51ms, 内存消耗: 8852KB, 提交时间: 2021-03-01
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int, int> P;
const int maxn = 54;
const int mod = 1000000007;
int ans, len1, len2;
bool a[maxn][maxn][maxn][maxn];
char str1[maxn], str2[maxn];
void solve(int l1, int r1, int l2, int r2)
{
ans = max(ans, r1-l1+1+r2-l2+1);
if(a[l1][r1][l2][r2])return;
a[l1][r1][l2][r2] = 1;
if(l1 == 0)
{
for(int i=1;i<=len1;i++)
{
if(str1[i] == str1[i+1])solve(i, i+1, l2, r2);
if(l2>1 && str1[i] == str2[l2-1])solve(i, i, l2-1, r2);
if(r2<len2 && str1[i] == str2[r2+1])solve(i, i, l2, r2+1);
}
}
if(l2 == 0)
{
for(int i=1;i<=len2;i++)
{
if(str2[i] == str2[i+1])solve(l1, r1, i, i+1);
if(l1>1 && str1[l1-1] == str2[i])solve(l1-1, r1, i, i);
if(r1<len1 && str1[r1+1] == str2[i])solve(l1, r1+1, i, i);
}
}
if(l1 > 1)
{
if(r1 < len1 && str1[l1-1] == str1[r1+1])solve(l1-1, r1+1, l2, r2);
if(l2!=0 && r2<len2 && str1[l1-1] == str2[r2+1])solve(l1-1, r1, l2, r2+1);
}
if(l2 > 1)
{
if(r2 < len2 && str2[l2-1] == str2[r2+1])solve(l1, r1, l2-1, r2+1);
if(l1!=0 && r1<len1 && str2[l2-1] == str1[r1+1])solve(l1, r1+1, l2-1, r2);
}
}
int main()
{
int t, n, m, i, j, k;
scanf("%d", &t);
while(t--)
{
memset(a, 0, sizeof(a));
ans = 0;
scanf("%s %s", str1+1, str2+1);
len1 = strlen(str1+1), len2 = strlen(str2+1);
for(i=1;i<=len1;i++)
{
solve(i, i, 0, 0);
if(str1[i] == str1[i+1]) solve(i, i+1, 0, 0);
}
for(i=1;i<=len2;i++)
{
solve(0, 0, i, i);
if(str2[i] == str2[i+1]) solve(0, 0, i, i+1);
}
for(i=1;i<=len1;i++)
for(j=1;j<=len2;j++)
if(str1[i] == str2[j]) solve(i, i, j, j);
printf("%d\n", ans);
}
return 0;
}