Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <vector>
- #include <algorithm>
- using namespace std;
- int main() {
- ios_base::sync_with_stdio(0), cin.tie(0);
- int n;
- cin >> n;
- vector<int> a(n);
- for (int i = 0; i < n; ++i)
- cin >> a[i];
- vector<vector<int>> dp(n, vector<int>(n, 0));
- int max_size = 0;
- for (int i = 0; i < n; ++i) {
- dp[i][i] = a[i];
- max_size = max(max_size, a[i]);
- }
- for (int length = 2; length <= n; ++length) {
- for (int i = 0; i + length - 1 < n; ++i) {
- int j = i + length - 1;
- for (int k = i; k < j; ++k) {
- if (dp[i][k] && dp[k + 1][j] && dp[i][k] == dp[k + 1][j]) {
- dp[i][j] = dp[i][k] + dp[k + 1][j];
- break;
- }
- }
- for (int k1 = i; k1 < j - 1 && dp[i][j] == 0; ++k1) {
- for (int k2 = k1 + 1; k2 < j; ++k2) {
- if (dp[i][k1] && dp[k1 + 1][k2] && dp[k2 + 1][j]
- && dp[i][k1] == dp[k2 + 1][j]) {
- dp[i][j] = dp[i][k1] + dp[k1 + 1][k2] + dp[k2 + 1][j];
- break;
- }
- }
- }
- max_size = max(max_size, dp[i][j]);
- }
- }
- cout << max_size << endl;
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement
