fork download
copy 
  1. #include <bits/stdc++.h> 
  2.  
  3. using namespace std;  
  4.  
  5. typedef long long ll;  
  6. typedef pair<int, int> ii;  
  7.  
  8. const int N = 2e3 + 5;  
  9.  
  10. int n;  
  11. string s;  
  12. int dp[N][N]; // dp[i][j] = Độ dài của xâu con đối xứng dài nhất khi xét đoạn [i..j] của xâu s 
  13.  
  14. // l   e    v     e   l     
  15. // i  i+1        j-1  j
  16.  
  17. int memo[N][N];   
  18.  
  19. int f(int i, int j) {
  20. 	if (i > j) return 0;   
  21. 	if (i == j) return 1;   
  22.  
  23. 	int& ans = memo[i][j];    
  24. 	if (ans != -1) return ans;   
  25.  
  26. 	if (s[i] == s[j]) {
  27. 		ans = 2 + f(i + 1, j - 1);   
  28. 	}
  29. 	else {
  30. 		ans = max(f(i + 1, j), f(i, j - 1)); 
  31. 	}
  32.  
  33. 	return ans;  
  34. }
  35.  
  36. void trace(int i, int j) {
  37. 	if (i > j) return;   
  38.  
  39. 	if (i == j) {
  40. 		cout << s[i]; 
  41. 		return; 
  42. 	}
  43.  
  44. 	if (s[i] == s[j]) {
  45. 		cout << s[i]; 
  46. 		trace(i + 1, j - 1);  
  47. 		cout << s[j]; 
  48. 	}
  49. 	else {
  50. 		if (f(i + 1, j) > f(i, j - 1)) {
  51. 			trace(i + 1, j); 
  52. 		}
  53. 		else {
  54. 			trace(i, j - 1); 
  55. 		}
  56. 	}
  57. }
  58.  
  59. int main() {
  60. 	ios::sync_with_stdio(false);
  61. 	cin.tie(nullptr);  	
  62. 	cin >> s; 
  63. 	n = s.size();  
  64.  
  65. 	s = ' ' + s;  
  66.  
  67. 	// thứ tự và chiều duyệt (xuôi/ngược) của vòng for sẽ dựa vào công thức truy hồi!
  68. 	// for (int i = n; i >= 1; i--) {
  69. 	// 	for (int j = i; j <= n; j++) {
  70. 	// 		if (i == j) {
  71. 	// 			dp[i][j] = 1;  
  72. 	// 			continue;  
  73. 	// 		}
  74. 	// 		if (s[i] == s[j]) {
  75. 	// 			dp[i][j] = dp[i + 1][j - 1] + 2; // xâu con đối xứng của đoạn [i+1..j-1] bổ sung thêm 2 kí tự vào 2 đầu
  76. 	// 		}
  77. 	// 		else { // s[i] != s[j]
  78. 	// 			dp[i][j] = max(dp[i + 1][j], dp[i][j - 1]); // xét trường hợp bỏ đi kí tự i hoặc bỏ đi kí tự j 
  79. 	// 		}
  80. 	// 	}
  81. 	// }
  82.  
  83. 	// cout << dp[1][n] << '\n'; 
  84.  
  85. 	memset(memo, -1, sizeof memo);  
  86.  
  87. 	trace(1, n); 
  88. }
  89.  
Success #stdin #stdout 0.01s 20632KB
comments (?)
stdin
copy 
lmevxeyzl
stdout
copy 
level
https://ideone.com/PfLxce
language:
C++14 (gcc 8.3)
created:
42 days ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!