题目

题目描述

涉及的知识点

区间dp: 在区间上进行动态规划，求解一段区间上的最优解。主要是通过合并小区间的最优解从而得出整个大区间上最优解的dp算法。

解题思路

第一步，数据不大，故建四维数组，设dp[l1][r1][l2][r2]表示a[l1…r1]和b[l2…r2]合并是否能组成回文串
第二步，当(r1-l1)+(r2-l2)<=1，dp[l1][r1][l2][r2]=1(即true)
第三步，转移方程：

1
2
3
4
5
6
7
8
//回文串最左边的字符a[l1]和最右边的字符a[r1]相等
dp[l1][r1][l2][r2] |= dp[l1+1][r1-1][l2][r2];
//回文串最左边的字符b[l2]和最右边的字符b[r2]相等
dp[l1][r1][l2][r2] |= dp[l1][r1][l2+1][r2-1];
//回文串最左边的字符a[l1]和最右边的字符b[r2]相等
dp[l1][r1][l2][r2] |= dp[l1+1][r1][l2][r2-1];
//回文串最左边的字符b[l2]和最右边的字符a[r1]相等
dp[l1][r1][l2][r2] |= dp[l1+1][r1-1][l2+1][r2];

ac代码

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
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const double pi=acos(-1),eps=1e-10;
const int inf=0x3f3f3f3f;
const int mod=1e9+7;

bool dp[55][55][55][55];

int main()
{
    int t;
    string a,b;
    cin>>t;
    while(t--){
        memset(dp,0,sizeof(dp));
        cin>>a>>b;
        a=" "+a,b=" "+b;
        int ans=0;
        int la=a.length()-1,lb=b.length()-1;
        for(int len1=0; len1<=la; len1++){
            for(int len2=0; len2<=lb; len2++){
                for(int l1=1,r1=l1+len1-1; r1<=la; l1++,r1++){
                    for(int l2=1,r2=l2+len2-1; r2<=lb; l2++,r2++){
                        if(len1+len2<=1)dp[l1][r1][l2][r2]=1;
                        else{
                            if(a[l1]==a[r1]&&r1>0)dp[l1][r1][l2][r2]|=dp[l1+1][r1-1][l2][r2];
                            if(a[l1]==b[r2]&&r2>0)dp[l1][r1][l2][r2]|=dp[l1+1][r1][l2][r2-1];
                            if(b[l2]==a[r1]&&r1>0)dp[l1][r1][l2][r2]|=dp[l1][r1-1][l2+1][r2];
                            if(b[l2]==b[r2]&&r2>0)dp[l1][r1][l2][r2]|=dp[l1][r1][l2+1][r2-1];
                        }
                        if(dp[l1][r1][l2][r2]){
                            ans=max(ans,r1-l1+r2-l2+2);
                        }
                    }}}}
        cout<<ans<<endl;

    }

    return 0;
}
/*


*/