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 INF = 1e9;  
  9. const ll LINF = 1e18;  
  10.  
  11. template<typename T>
  12. void minimize(T& a, const T& b) {
  13. 	if (b < a) a = b; 
  14. }
  15.  
  16. const int N = 5e2 + 5; 
  17.  
  18. int n; 
  19. int c[N]; 
  20.  
  21. // dp(l, r, palin) = Chi phí ít nhất để xoá hết đoạn [l, r] và trước đó có đang duy trì xâu đối xứng nào hay không
  22. int memo[N][N][2];  
  23.  
  24. int dp(int l, int r, bool palin) {
  25. 	if (l > r) return 0;
  26. 	if (l == r) return (!palin); 
  27.  
  28. 	int& ans = memo[l][r][palin]; 
  29. 	if (ans != -1) return ans; 
  30.  
  31. 	ans = INF;   
  32. 	// Trường hợp xoá 1 kí tự
  33. 	for (int k = l; k <= r; k++) {
  34. 		if (palin) {
  35. 			minimize(ans, 1 + dp(l, k - 1, 1) + dp(k + 1, r, 0)); 
  36. 			minimize(ans, 1 + dp(l, k - 1, 0) + dp(k + 1, r, 1)); 
  37. 		}
  38. 		else {
  39. 			minimize(ans, 1 + dp(l, k - 1, 0) + dp(k + 1, r, 0)); 
  40. 		}
  41. 	}
  42.  
  43. 	// Trường hợp chọn ra cặp (c[l], c[k]) để bổ sung vào xâu đối xứng đang duy trì trước đó nếu có,
  44. 	// nếu không thì tạo mới một xâu đối xứng
  45. 	for (int k = l + 1; k <= r; k++) {
  46. 		if (c[l] == c[k]) {
  47. 			minimize(ans, (!palin) + dp(l + 1, k - 1, 1) + dp(k + 1, r, 0)); 
  48. 		}
  49. 	}
  50.  
  51. 	return ans; 
  52. }
  53.  
  54. int main() {
  55. 	ios::sync_with_stdio(false); 
  56. 	cin.tie(nullptr); 	
  57. 	cin >> n; 
  58. 	for (int i = 1; i <= n; i++) cin >> c[i]; 
  59.  
  60. 	memset(memo, -1, sizeof memo); 
  61. 	cout << dp(1, n, 0) << '\n'; 
  62. }
Success #stdin #stdout 0.01s 5660KB
comments (?)
stdin
copy 
3
1 2 1
stdout
copy 
1
https://ideone.com/7Bv0Wm
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!