[USACO16OPEN]262144

題目鏈接：點這里

Solution:

設\(f[i][j]\)表示以j為左端點，合并后最大值為i的序列的右端點的位置

那么我們可以得到狀態轉移方程\(f[i][j]=f[i-1][f[i-1][j]+1]\)

因為\(N\le262144\)，所以i最大可能為58，那么我們枚舉即可

Code：

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=262146;
int n,ans,f[59][N];
int read(){int x=0,f=1;char ch=getchar();while(!isdigit(ch)){if(ch=='-')f=-f;ch=getchar();}while(isdigit(ch)){x=x*10+ch-48;ch=getchar();}return x*f;
}
int main(){n=read();for(int i=1;i<=n;i++) f[read()][i]=i;for(int i=1;i<=58;i++) for(int j=1;j<=n;j++){!f[i][j]&&f[i-1][j]&&(f[i][j]=f[i-1][f[i-1][j]+1]);f[i][j]?ans=i:0;}printf("%d\n",ans);return 0;
}