P3147 [USACO16OPEN]262144 P

方杰123 · 2022-10-15 12:58:56 · 个人记录

题目

思路

一眼区间DP。 二眼数据范围。设计f[i][j]表示区间[i,j] 肯定是不行了。然后我们发现，其实合并的断点是一定的，区间长度是一定的，也就是说，想合并一个数，那么它的长度为定值，所以只要表示它的起点即可。设计f[i][j]表示起点为i，合成j时是否可能，不可能为0，可能的话为了方便记录一下右端点。

code

#include<bits/stdc++.h>
using namespace std;
const int N=3e5+10;
int read(){
    int x=0,f=1;char c=getchar();
    while(c>'9' || c<'0'){if(c=='-')f=-1;c=getchar();}
    while(c>='0' && c<='9'){x=(x<<1)+(x<<3)+(c^48);c=getchar();}
    return x*f;
}
int n,a[N],f[N][110],ans;
int main(){
    n=read();
    for(int i=1;i<=n;i++){
        a[i]=read();
        f[i][a[i]]=i;
    }
    for(int i=1;i<=100;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;
        }
    }
    printf("%d",ans);
    return 0;
}