题解

设 dp[v][i] 为：从位置 i 开始的某个连续段能被不断合并成数值 v 时，这段的最右端位置的最小可能值；若不存在则记为无穷大。初始时，当且仅当 a[i] = v 时 dp[v][i] = i。

若一段能合成 v+1，则它可由两段连续的值为 v 的区间拼起来，即 dp[v][i] 和 dp[v][dp[v][i]+1] 都合法时，dp[v+1][i] = min(dp[v+1][i], dp[v][dp[v][i]+1])。按位置从后往前扫即可确保右端信息已被计算。值域只有 $40$，整体复杂度 $\mathcal{O}(40n)$，内存 $\mathcal{O}(40n)$。

最后寻找最大的 v 使得存在某个 i 满足 dp[v][i] 有效，即为答案。

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    if (!(cin >> n)) return 0;
    vector<int> a(n + 1);
    for (int i = 1; i <= n; ++i) cin >> a[i];
    const int MAXV = 40;
    const int INF = n + 5;
    vector<vector<int>> dp(MAXV + 1, vector<int>(n + 2, INF));
    for (int i = 1; i <= n; ++i) {
        dp[a[i]][i] = i;
    }
    for (int v = 2; v <= MAXV; ++v) {
        for (int i = n; i >= 1; --i) {
            int mid = dp[v - 1][i];
            if (mid < INF && mid + 1 <= n) {
                int right = dp[v - 1][mid + 1];
                if (right < INF) dp[v][i] = min(dp[v][i], right);
            }
        }
    }
    int ans = 0;
    for (int v = 1; v <= MAXV; ++v) {
        bool ok = false;
        for (int i = 1; i <= n; ++i) {
            if (dp[v][i] < INF) {
                ok = true;
                break;
            }
        }
        if (ok) ans = v;
    }
    cout << ans << '\n';
    return 0;
}