首页 > itarticle > usaco16open 262144

usaco16open 262144

admin 1月 18, 2021 0

题解

奇妙的做法。
考虑倍增，由于合并必然是一整段连续的序列，所以
设$f(i,j)$表示从$j$开始一直合并，直到出现$i$时的下标（开）。
然后就可以倍增了。


#include <cstdlib>
#include <algorithm>
#include <cstring>
#include <cctype>
using namespace std;
typedef long long ll;
int f[65][270000]={0},n,ans=0;
void (){
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        int u;
        scanf("%d",&u),f[u][i]=i+1;
        ans=max(ans,u);
    }
}
void solve(){
    for(int i=2;i<=60;i++){
        for(int j=1;j<=n;j++){
            if(!f[i][j]&&f[i-1][j]&&f[i-1][f[i-1][j]])
                f[i][j]=f[i-1][f[i-1][j]],
                ans=max(ans,i);
        }
    }
    printf("%dn",ans);
}
int main(){
    init();
    solve();
    return 0;
}