美團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;
}