A2184 [USACO16OPEN] 262144 P

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N;
    cin >> N;
    vector<int> a(N + 1);
    for (int i = 1; i <= N; i++) cin >> a[i];

    const int MAXV = 60;
    // dp[i][v]：从 i 开始的连续段合并成 v 之后，这一段的右端点；0 表示不存在
    vector<vector<int>> dp(N + 2, vector<int>(MAXV + 1, 0));

    int answer = 0;
    for (int i = N; i >= 1; i--) {
        for (int v = a[i]; v <= MAXV; v++) {
            if (v == a[i]) {
                dp[i][v] = i;
            } else {
                // 合并成 v 的最后一步，一定是左右两段各合并成 v-1
                int e = dp[i][v - 1];
                if (e != 0 && dp[e + 1][v - 1] != 0) {
                    dp[i][v] = dp[e + 1][v - 1];
                }
            }
            if (dp[i][v] != 0) answer = max(answer, v);
        }
    }

    cout << answer << "\n";
    return 0;
}