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, carry) = 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 carry) {
  25. 	if (l > r) return 0;
  26. 	if (l == r) return (!carry); 
  27.  
  28. 	int& ans = memo[l][r][carry]; 
  29. 	if (ans != -1) return ans; 
  30.  
  31. 	// Cặp (c[l], c[k]) sẽ bổ sung vào xâu đối xứng đang duy trì trước đó nếu có,
  32. 	// nếu không thì tạo mới một xâu đối xứng
  33. 	ans = INF;   
  34. 	for (int k = l; k <= r; k++) {
  35. 		if (c[l] == c[k]) {
  36. 			minimize(ans, (!carry) + dp(l + 1, k - 1, 1) + dp(k + 1, r, 0)); 
  37. 		}
  38. 	}
  39.  
  40. 	return ans; 
  41. }
  42.  
  43. int main() {
  44. 	ios::sync_with_stdio(false); 
  45. 	cin.tie(nullptr); 	
  46. 	cin >> n; 
  47. 	for (int i = 1; i <= n; i++) cin >> c[i]; 
  48.  
  49. 	memset(memo, -1, sizeof memo); 
  50.  
  51. 	cout << dp(1, n, 0) << '\n'; 
  52. }
Success #stdin #stdout 0.01s 5524KB
comments (?)
stdin
copy 
3
1 2 1
stdout
copy 
1
https://ideone.com/KyQnrA
language:
C++14 (gcc 8.3)
created:
19 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!