9.28金山笔试题解

分析题解攒人品~求池子里的ocococococ😭😭😭

主要是说下第三题吧

题意：给两个字符串AB，求生成的新字符串的最长回文子串长度，生成的规则是AB字符串任意拼接生成C，只要保证A是C的子序列，B是C的子序列即可。AB长度<=50

思路：设dp[i][j][l][r]，表示使用A的[i,j]区间B的[l,r]区间，能构造出的最长回文字符串长度

类似区间dp吧，代码更直观一点

#include <iostream>
#include <bits/stdc++.h>
// #define int long long
#define endl '\n'
using namespace std;
const int N = 60;
int f[N][N][N][N];
void solve(){
    memset(f, 0, sizeof(f));
    string s1,s2;
    cin >> s1 >> s2;
    int n = s1.size();
    int m = s2.size();
    s1 = ' ' + s1;
    s2 = ' ' + s2;
    for(int i=1; i<=n; i++){
        for(int j=1;j<=m+1;j++){
            f[i][i][j][j-1] = 1;
        }
    }

    for(int i=1; i<=m; i++){
        for(int j=0;j<=n+1;j++){
            for(int k=0;k<=n+1;k++){
                if(j==k and j and j<=n and s1[j] == s2[i]){
                    f[j][k][i][i] = 2;
                }
                else {
                    if(k==j-1)
                        f[j][k][i][i] = 1;
                }
            }
        }
    }
    for(int len1=0; len1<=n; len1++){
        for(int len2=0; len2<=m; len2++){
            for(int i=1,j=len1; j<=n; i++, j++){
                for(int l=1,r=len2; r<=m; l++,r++){
                    if(!f[i][j][l][r] and (len1!=0 or len2!=0)) continue;
                    if(i-1 >= 1 and j+1 <=n and s1[i-1] == s1[j+1])
                        f[i-1][j+1][l][r] = max(f[i][j][l][r]+2, f[i-1][j+1][l][r]);
                    if(i-1 >= 1 and r+1 <=m and s1[i-1] == s2[r+1])
                        f[i-1][j][l][r+1] = max(f[i][j][l][r]+2, f[i-1][j][l][r+1]);
                    if(l-1 >= 1 and j+1 <=n and s2[l-1] == s1[j+1])
                        f[i][j+1][l-1][r] = max(f[i][j][l][r]+2, f[i][j+1][l-1][r]);
                    if(l-1 >= 1 and r+1 <=m and s2[l-1] == s2[r+1])
                        f[i][j][l-1][r+1] = max(f[i][j][l][r]+2, f[i][j][l-1][r+1]);
                }
            }
        }
    }
    int ans = 0;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            for(int l=1;l<=m;l++){
                for(int r=1;r<=m;r++){
                    ans = max(ans, f[i][j][l][r]);
                }
            }
        }
    }
    cout << ans << endl;
}
signed main() {
    int T;cin>>T;
    while(T--){
        solve();
    }
}