fork download
copy 
  1. #include <bits/stdc++.h> 
  2. using namespace std;  
  3.  
  4. typedef long long ll;  
  5. typedef pair<int, int> ii;  
  6.  
  7. const int N = 2e3 + 5;  
  8.  
  9. int n;  
  10. string s;  
  11. int dp[N][N]; // dp[i][j]: là độ 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 
  12.  
  13. // đáp án: dp[1][n] 
  14.  
  15. // l   e    v     e   l     
  16. // i  i+1        j-1  j
  17.  
  18. int memo[N][N];   
  19.  
  20. int f(int i, int j) {
  21. 	if (i > j) return 0;   
  22. 	if (i == j) return 1;   
  23.  
  24. 	int& ans = memo[i][j];    
  25. 	if (ans != -1) return ans;   
  26.  
  27. 	if (s[i] == s[j]) {
  28. 		ans = 2 + f(i + 1, j - 1);   
  29. 	}
  30. 	else {
  31. 		ans = max(f(i + 1, j), f(i, j - 1)); 
  32. 	}
  33.  
  34. 	return ans;  
  35. }
  36.  
  37. void trace(int i, int j) {
  38. 	if (i > j) return;   
  39.  
  40. 	if (i == j) {
  41. 		cout << s[i]; 
  42. 		return; 
  43. 	}
  44.  
  45. 	if (s[i] == s[j]) {
  46. 		cout << s[i]; 
  47. 		trace(i + 1, j - 1);  
  48. 		cout << s[j]; 
  49. 	}
  50. 	else {
  51. 		if (f(i + 1, j) > f(i, j - 1)) {
  52. 			trace(i + 1, j); 
  53. 		}
  54. 		else {
  55. 			trace(i, j - 1); 
  56. 		}
  57. 	}
  58. }
  59.  
  60. int main() {
  61. 	ios::sync_with_stdio(0); cin.tie(0);  	
  62. 	cin >> s; 
  63. 	n = s.size();  
  64.  
  65. 	s = ' ' + s;  
  66.  
  67. 	// thứ tự 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. 	cout << '\n'; 
  90. }
  91.  
Success #stdin #stdout 0.01s 19680KB
comments (?)
stdin
copy 
lmevxeyzl
stdout
copy 
level
https://ideone.com/ejYPRv
language:
C++14 (gcc 8.3)
created:
1 year 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!