Link

这个题有一个很特殊的点，就是最大值不会超过28，可以想一下最多可以合并多少次。

那么常规的区间dp是不能使用的，就要采用特殊的形式，

$dp_{i,j}$ 表示$i$在左边，达到$j$的话的右端点位置

$dp{i,j}=dp{dp_{i,j-1}+1,j-1}$

然后转移就可以了.

#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<queue>
#include<stack>
#include<set>
#include<map>
#include<ctime>
#include<bitset>
using namespace std;
int n;
int a[262145];
int h;
int ans;
int f[300000][80];
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;++i){
        scanf("%d",&a[i]);
        f[i][a[i]]=i;
    }
    for(int i=1;i<=58;++i){
        for(int j=1;j<=n;++j){
            if(!f[j][i]&&f[j][i-1])
                f[j][i]=f[f[j][i-1]+1][i-1];
            if(f[j][i])
            ans=i;
        }
    }
    cout<<ans;
    return 0;
}
```P3147 [USACO16OPEN] 262144 P