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 maximize(T& a, const T& b) {
  13. 	if (a < b) a = b;  
  14. }
  15.  
  16. const int N = 3e2 + 5; 
  17.  
  18. int n; 
  19. int a[N]; 
  20.  
  21. int number_of_subtask() {
  22. 	if (n <= 10) return 1; 
  23. 	return 2; 
  24. }
  25.  
  26. namespace sub1 {
  27. 	int ans;  
  28.  
  29. 	bool removed[11];  
  30.  
  31. 	void backtrack(int step) {
  32. 		if (step == n) return;   
  33.  
  34. 		for (int i = 1; i + 1 <= n; i++) {
  35. 			if (removed[i]) continue; 
  36. 			for (int j = i + 1; j <= n; j++) {
  37. 				if (!removed[j]) {
  38. 					if (a[i] == a[j]) {
  39. 						a[i] += 2;  
  40. 						removed[j] = true;
  41. 						maximize(ans, a[i]);   
  42. 						backtrack(step + 1); 
  43. 						removed[j] = false; 
  44. 						a[i] -= 2; 
  45. 					}
  46. 					break; 
  47. 				}
  48. 			}
  49. 		}
  50. 	}
  51.  
  52. 	void solve() {
  53. 		ans = 0;  
  54. 		for (int i = 1; i <= n; i++) maximize(ans, a[i]); 
  55. 		backtrack(0);
  56. 		cout << ans << '\n';  
  57. 	}
  58. }
  59.  
  60. namespace sub2 {
  61. 	// dp(l, r) = Giá trị v lớn nhất đạt được khi gộp đoạn [l, r] về thành 1 phần tử
  62. 	int memo[N][N]; 
  63.  
  64. 	int dp(int l, int r) {
  65. 		if (l == r) return a[l]; 
  66.  
  67. 		int& ans = memo[l][r];
  68. 		if (ans != -1) return ans; 
  69.  
  70. 		ans = 0; 
  71. 		for (int k = l; k < r; k++) {
  72. 			int u = dp(l, k), v = dp(k + 1, r); 
  73. 			if (u == v) maximize(ans, u + 2); 
  74. 		}
  75.  
  76. 		return ans; 
  77. 	}
  78.  
  79. 	void solve() {
  80. 		memset(memo, -1, sizeof memo); 
  81.  
  82. 		int ans = 0; 
  83. 		for (int l = 1; l <= n; l++) {
  84. 			for (int r = l; r <= n; r++) {
  85. 				maximize(ans, dp(l, r)); 
  86. 			}
  87. 		}
  88.  
  89. 		cout << ans << '\n'; 
  90. 	}
  91. }
  92.  
  93.  
  94. int main() {
  95. 	ios::sync_with_stdio(false); 
  96. 	cin.tie(nullptr); 	
  97. 	cin >> n; 
  98. 	for (int i = 1; i <= n; i++) cin >> a[i]; 
  99.  
  100. 	int subtask = number_of_subtask(); 
  101.  
  102. 	if (subtask == 1) sub1::solve(); 
  103. 	if (subtask == 2) sub2::solve();   
  104. }
Success #stdin #stdout 0.01s 5272KB
comments (?)
stdin
copy 
4
1 1 1 3
stdout
copy 
5
https://ideone.com/mG7T5y
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!