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ị thu được khi gộp đoạn [l, r] của mảng a về thành 1 phần tử
  62. 	// Fact: Lý do không có từ "lớn nhất" trong lời gọi dp là vì
  63. 	//       nếu có nhiều cách gộp đoạn [l, r] về thành 1 phần tử thì giá trị thu được sau cùng là như nhau cho mọi cách 
  64. 	int memo[N][N]; 
  65.  
  66. 	int dp(int l, int r) {
  67. 		if (l == r) return a[l]; 
  68.  
  69. 		int& ans = memo[l][r];
  70. 		if (ans != -1) return ans; 
  71.  
  72. 		ans = 0; 
  73. 		for (int k = l; k < r; k++) {
  74. 			int u = dp(l, k), v = dp(k + 1, r); 
  75. 			if (u == v && u != 0) ans = u + 2; 
  76. 		}
  77.  
  78. 		return ans; 
  79. 	}
  80.  
  81. 	void solve() {
  82. 		memset(memo, -1, sizeof memo); 
  83.  
  84. 		int ans = 0; 
  85. 		for (int l = 1; l <= n; l++) {
  86. 			for (int r = l; r <= n; r++) {
  87. 				maximize(ans, dp(l, r)); 
  88. 			}
  89. 		}
  90.  
  91. 		cout << ans << '\n'; 
  92. 	}
  93. }
  94.  
  95.  
  96. int main() {
  97. 	ios::sync_with_stdio(false); 
  98. 	cin.tie(nullptr); 	
  99. 	cin >> n; 
  100. 	for (int i = 1; i <= n; i++) cin >> a[i]; 
  101.  
  102. 	int subtask = number_of_subtask(); 
  103.  
  104. 	if (subtask == 1) sub1::solve(); 
  105. 	if (subtask == 2) sub2::solve();   
  106. }
Success #stdin #stdout 0s 5316KB
comments (?)
stdin
copy 
4
1 1 1 3
stdout
copy 
5
https://ideone.com/S9c59l
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!