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 a[N]; 
  20.  
  21. // dp(l, r) = Giá trị thu được khi gộp đoạn [l, r] của mảng a về thành 1 phần tử
  22. int memo[N][N]; 
  23.  
  24. int dp(int l, int r) {
  25. 	if (l == r) return a[l]; 
  26.  
  27. 	int& ans = memo[l][r]; 
  28. 	if (ans != -1) return ans;   
  29.  
  30. 	ans = 0;  
  31. 	for (int k = l; k < r; k++) {
  32. 		int u = dp(l, k), v = dp(k + 1, r); 
  33. 		if (u == v && u != 0) ans = u + 1; 
  34. 	}
  35.  
  36. 	return ans; 	
  37. }
  38.  
  39. int f[N]; // f[i] = Độ dài tối thiểu của mảng a[1..i] sau khi thực hiện thao tác
  40.  
  41. int main() {
  42. 	ios::sync_with_stdio(false); 
  43. 	cin.tie(nullptr); 	
  44. 	cin >> n; 
  45. 	for (int i = 1; i <= n; i++) cin >> a[i]; 
  46.  
  47. 	memset(memo, -1, sizeof memo);  
  48.  
  49. 	for (int i = 1; i <= n; i++) {
  50. 		f[i] = INF; 
  51. 		for (int j = 0; j < i; j++) {
  52. 			if (dp(j + 1, i) != 0) minimize(f[i], f[j] + 1); 
  53. 		}
  54. 	}
  55.  
  56. 	cout << f[n] << '\n'; 
  57. }
Success #stdin #stdout 0.01s 5288KB
comments (?)
stdin
copy 
5
4 3 2 2 3
stdout
copy 
2
https://ideone.com/myi7Gr
language:
C++14 (gcc 8.3)
created:
20 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!