传送门: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 }
内容来源于网络如有侵权请私信删除
- 还没有人评论，欢迎说说您的想法！
客服
