合并回文子串（区间dp）

题目链接.

$dp[l1][r1][l2][r2]$表示字符串$s1$的$l1-r1$和字符串$s2$的$l2-r2$能否组成回文串。

对于$dp[l1][r1][l2][r2]$共有四种可能的转移：

$dp[l1+1][r1-1][l2][r2];$

$dp[l1+1][r1][l2][r2-1];$

$dp[l1][r1-1][l2+1][r2];$

$dp[l1][r1][l2+1][r2-1];$

#include
#define ll long long
using namespace std;
const int N=10010;

char s1[55],s2[55];
bool dp[55][55][55][55];

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);

    int t;cin>>t;
    while(t--)
    {
        cin>>s1+1>>s2+1;
        int n1=strlen(s1+1);
        int n2=strlen(s2+1);

        int ans=1;
        for(int len1=0;len1<=n1;len1++)
        {
            for(int len2=0;len2<=n2;len2++)
            {
                for(int l1=1,r1=l1+len1-1;r1<=n1;l1++,r1++)
                {
                    for(int l2=1,r2=l2+len2-1;r2<=n2;l2++,r2++)
                    {
                        dp[l1][r1][l2][r2]=0;
                        bool &v=dp[l1][r1][l2][r2];
                        if(len1+len2<=1)v=1;
                        else
                        {
                            if(s1[l1]==s1[r1]&&r1>0)v|=dp[l1+1][r1-1][l2][r2];
                            if(s1[l1]==s2[r2]&&r2>0)v|=dp[l1+1][r1][l2][r2-1];
                            if(s2[l2]==s1[r1]&&r1>0)v|=dp[l1][r1-1][l2+1][r2];
                            if(s2[l2]==s2[r2]&&r2>0)v|=dp[l1][r1][l2+1][r2-1];
                        }
                        //该序列可以组成回文串
                        if(v)ans=max(ans,r1-l1+r2-l2+2);
                    }
                }
            }
        }
        cout<<ans<<"\n";
    }
    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50