美团CodeM 初赛 A伦 合并回文子串 区间dp

[编程题] 合并回文子串

时间限制：2秒

空间限制：262144K

输入两个字符串A和B，合并成一个串C，属于A和B的字符在C中顺序保持不变。如"abc"和"xyz"可以被组合成"axbycz"或"abxcyz"等。

我们定义字符串的价值为其最长回文子串的长度（回文串表示从正反两边看完全一致的字符串，如"aba"和"xyyx"）。

需要求出所有可能的C中价值最大的字符串，输出这个最大价值即可 

输入描述:

第一行一个整数T(T ≤ 50)。
接下来2T行，每两行两个字符串分别代表A,B(|A|,|B| ≤ 50)，A,B的字符集为全体小写字母。      

输出描述:

对于每组数据输出一行一个整数表示价值最大的C的价值。      

输入例子:

2
aa
bb
a
aaaabcaa      

输出例子:

4      

1可以想到一个dp：  dp[l1][r1][l2][r2].但是我一开始把这个dp定义为，，A中的[l1,r1]和B中的[l2,r2]能合成的回文串长度最多是多少。。。乍一看好像没什么问题，，然后我就往下敲了，，，结果敲了半天答案不对。。输出了一下中间过程，才发现不能这么定义dp。。。然后纠结了一会改成了  A中的[l1,r1]和B中的[l2,r2]能否合成一个回文串。这样就没问题了。

#include<iostream>
#include<cstdio>
#include<math.h>
#include<algorithm>
#include<map>
#include<set>
#include<bitset>
#include<stack>
#include<queue>
#include<string.h>
#include<cstring>
#include<vector>
#include<time.h>
#include<stdlib.h>
using namespace std;
#define INF 0x3f3f3f3f
#define INFLL 0x3f3f3f3f3f3f3f3f
#define FIN freopen("input.txt","r",stdin)
#define mem(x,y) memset(x,y,sizeof(x))
typedef unsigned long long ULL;
typedef long long LL;
#define fuck(x) cout<<"q"<<endl;
#define MX 55
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
typedef pair<pair<int,int>,int> PIII;
typedef pair<int,int> PII;
const double eps=1e-8;
int n;
bool dp[MX][MX][MX][MX];
char a[MX],b[MX];
int main()
{
    FIN;
    int T;
    cin>>T;
    while(T--)
    {
        cin>>a+1>>b+1;
        int la=strlen(a+1),lb=strlen(b+1);
        for(int l1=0; l1<=la; l1++)
            for(int r1=l1; r1<=la; r1++)
                for(int l2=0; l2<=lb; l2++)
                    for(int r2=l2; r2<=lb; r2++)
                        if(l1==r1&&l2==r2)dp[l1][r1][l2][r2]=1;
                        else if((r1-l1==1&&l2==r2)||(r2-l2==1&&l1==r1))dp[l1][r1][l2][r2]=1;
                        else dp[l1][r1][l2][r2]=0;
        //cout<<dp[0][0][0][0]<<endl;
        int ans=0;
        for(int d1=0; d1<=la; d1++)
            for(int l1=0; l1+d1<=la; l1++)
            {
                int r1=l1+d1;
                for(int d2=0; d2<=lb; d2++)
                    for(int l2=0; l2+d2<=lb; l2++)
                    {
                        int r2=l2+d2;
                        bool t1=0,t2=0,t3=0,t4=0;
                        if(l1!=r1&&l2!=r2&&a[l1+1]==b[r2]) t1=dp[l1+1][r1][l2][r2-1];
                        if(l1!=r1&&l2!=r2&&a[r1]==b[l2+1]) t2=dp[l1][r1-1][l2+1][r2];
                        if(r1-l1>1&&a[l1+1]==a[r1])t3=dp[l1+1][r1-1][l2][r2];
                        if(r2-l2>1&&b[l2+1]==b[r2])t4=dp[l1][r1][l2+1][r2-1];
                        dp[l1][r1][l2][r2]|=t1|t2|t3|t4;
                        //printf("val=%d,(%d,%d) (%d,%d) t1=%d,t2=%d,t3=%d,t4=%d\n",dp[l1][r1][l2][r2],l1,r1,l2,r2,t1,t2,t3,t4);
                        if(dp[l1][r1][l2][r2])ans=max(ans,r1-l1+r2-l2);
                    }
            }
        cout<<ans<<endl;
    }
    return 0;
}