看到$c_i$的数据范围你是不是明白了什么
（其实这种题常规写法不是区间dp吗）
但是区间dp $O(N^3)$ 显然过不去
*我们考虑一下把值域丢到状态中
设$dp_{i,j}$表示第i个数，向右合并到哪能得到j
然后就可以得到$$dp_{i,j+1}=dp_{dp_{i,j}+1,j}$$
1 #include<bits/stdc++.h> 2 using namespace std; 3 #define ll long long 4 inline ll read() { 5 ll x=0,f=1; char ch=getchar(); 6 for(;ch<'0'||ch>'9';ch=getchar()) 7 if(ch=='-')f=-f; 8 for(;ch>='0'&&ch<='9';ch=getchar()) 9 x=x*10+ch-'0'; 10 return x*f; 11 } 12 inline void chkmin( int &a,int b ) { if(a>b) a=b; } 13 inline void chkmax( int &a,int b ) { if(a<b) a=b; } 14 #define _ read() 15 #define ln endl 16 const int N=262150; 17 int n,a[N],dp[N][60]; 18 int main() { 19 n=_; 20 for( int i=1;i<=n;i++ ) a[i]=_,dp[i][a[i]]=i; 21 for( int j=1;j<=58;j++ ) 22 for( int i=1;i<=n;i++ ) 23 if(!dp[i][j]); 24 else dp[i][j+1]=dp[dp[i][j]+1][j]; 25 for( int j=58;j;j-- ) 26 for( int i=1;i<=n;i++ ) 27 if(dp[i][j]) { cout<<j; return 0; } 28 // cout<<dp[i][2]<<" "; 29 30 }