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(); } }