Educational Codeforces Round 158 (Rated for Div. 2)D

题意思路维护前后缀最大值选某个点作为起点的时候只考虑一侧的最大值因为只能连续清除那么考虑枚举i最大值只能出现在3种情况1.本身2.把i以及左侧清理完加上suf[i1]最大值产生在右侧3.把i以及右侧清理完加上pre[i-1]最大值产生在左侧#includebits/stdc.h #define int long long #define fi first #define se second #define endl \n using namespace std; typedef pairint,int pii; const int N1e610; const int mod998244353; vectorintpm; int judge[N],nm[N],inv[N]; int Log2[N]; int kmi(int a,int b){ int res1; while(b){ if(b1) resres*a%mod; aa*a%mod; b1; } return res; } void init(){ nm[0]inv[0]1; for(int i1;i1e6;i){ nm[i]nm[i-1]*i%mod; inv[i]kmi(nm[i],mod-2); } } void euler(int n){ judge[1]1; for(int i2;in;i){ if(!judge[i]){ pm.push_back(i); } for(int j0;pm[j]*in;j){ judge[pm[j]*i]1; if(i%pm[j]0) break; } } } int C(int a,int b){ return nm[a]*inv[a-b]%mod*inv[b]%mod; } // struct nod{ // int p,val; // bool operator(const nod b)const{ // return valb.val; // } // }; //维护单边最大值枚举i假设删除掉i以及左边所有元素 void solve(){ int n;cinn; vectorinta(n10),pre(n10),suf(n10); for(int i1;in;i) cina[i]; int ans1e18; for(int i1;in;i){ pre[i]max(pre[i-1]1,a[i]); } for(int in;i1;i--){ suf[i]max(suf[i1]1,a[i]); } for(int i1;in;i){ int mxmax({a[i],suf[i1]i-1,pre[i-1]n-i1}); ansmin(ans,mx); } coutans; } signed main(){ ios::sync_with_stdio(0);cin.tie(0); // for(int i2;i1e6;i){ // Log2[i]Log2[i/2]1; // } int T1;//cinT; while(T--) solve(); return 0; }