传送门:https://www.nowcoder.com/activity/2017codem/oj
输入例子:
2
aa
bb
a
aaaabcaa
输出例子:
4
5
题解:dp,i代表a串开始的位置,j代表b串开始的位置,da,db分别代表在a和b中的长度,dp[x][y][z][h]代表 a中选下标为x到y-1的串 和 b中选z到h-1的串是否可以组合成回文串。利用每个字符串的长度更新dp[i][i + da][j][j + db]
初始状态 da+db<=1时必为true
更新四种状态 a或b中任意一组 首位和末位相同时 可以进行更新。存在四种情况 a[i] == a[i + da - 1] 或b[j] == b[j + db - 1]或a[i] == b[j + db - 1]或b[j] == a[i + da - 1]。
注意:不能用memset每次对dp处理 会TLE。需要在每次更新时先设置值。
1 #define _CRT_SECURE_NO_DEPRECATE
2 #pragma comment(linker, "/STACK:102400000,102400000")
3 #include<iostream>
4 #include<cstdio>
5 #include<fstream>
6 #include<iomanip>
7 #include<algorithm>
8 #include<cmath>
9 #include<deque>
10 #include<vector>
11 #include<assert.h>
12 #include<bitset>
13 #include<queue>
14 #include<string>
15 #include<cstring>
16 #include<map>
17 #include<stack>
18 #include<set>
19 #include<functional>
20 #define pii pair<int, int>
21 #define mod 1000000007
22 #define mp make_pair
23 #define pi acos(-1)
24 #define eps 0.00001
25 #define mst(a,i) memset(a,i,sizeof(a))
26 #define all(n) n.begin(),n.end()
27 #define lson(x) ((x<<1))
28 #define rson(x) ((x<<1)|1)
29 #define inf 0x3f3f3f3f
30 typedef long long ll;
31 typedef unsigned long long ull;
32 using namespace std;
33 const int maxn = 55;
34 int dp[maxn][maxn][maxn][maxn];
35
36 int main()
37 {
38 ios::sync_with_stdio(false);
39 cin.tie(0); cout.tie(0);
40 int i, j, k, m, n, T;
41 cin >> T;
42 string a, b;
43 while (T--)
44 {
45 int ans = 0;
46 cin >> a >> b;
47 for (int da = 0; da <= a.size(); ++da)
48 for (int db = 0; db <= b.size(); ++db)
49 for (int i = 0; da + i <= a.size(); ++i)
50 for (int j = 0; db + j <= b.size(); ++j)
51 {
52 if (da + db <= 1)
53 dp[i][i + da][j][j + db] = 1;
54 else
55 {
56 dp[i][i + da][j][j + db] = 0; //替代memset
57 if (da >= 2 && a[i] == a[i + da - 1])
58 dp[i][i + da][j][j + db] |= dp[i + 1][i + da - 1][j][j + db];
59 if (db >= 2 && b[j] == b[j + db - 1])
60 dp[i][i + da][j][j + db] |= dp[i][i + da][j + 1][j + db - 1];
61 if (db >= 1 && da >= 1 && a[i] == b[j + db - 1])
62 dp[i][i + da][j][j + db] |= dp[i + 1][i + da][j][j + db - 1];
63 if (db >= 1 && da >= 1 && b[j] == a[i + da - 1])
64 dp[i][i + da][j][j + db] |= dp[i][i + da - 1][j + 1][j + db];
65 }
66 if (dp[i][i + da][j][j + db])ans = max(ans, da + db);
67 }
68 cout << ans << endl;
69 }
70 return 0;
71 }
转载于:https://www.cnblogs.com/Meternal/p/7064429.html