Codeforces - DZY Loves Sequences

tech2025-02-08  11

题目链接:Codeforces - DZY Loves Sequences


做一个前后缀连续 LIS ,然后枚举每个位置即可。

注意细节。


AC代码:

#pragma GCC optimize("-Ofast","-funroll-all-loops") #include<bits/stdc++.h> //#define int long long using namespace std; const int N=1e5+10; int n,a[N],f[N],g[N],res; signed main(){ cin>>n; if(n==1) return puts("1"),0; for(int i=1;i<=n;i++) scanf("%d",&a[i]); for(int i=1;i<=n;i++) f[i]=(a[i]>a[i-1]?f[i-1]+1:1); for(int i=n;i>=1;i--) g[i]=(a[i]<a[i+1]?g[i+1]+1:1); for(int i=1;i<=n;i++) res=max(res,max(f[i],g[i])); if(a[2]<=a[1]) res=max(res,1+g[2]); if(a[n]<=a[n-1]) res=max(res,1+f[n-1]); for(int i=1;i<=n;i++) if(a[i-1]+1<a[i+1]) res=max(res,f[i-1]+g[i+1]+1); for(int i=1;i<n;i++) res=max(res,f[i]+1); for(int i=2;i<=n;i++) res=max(res,g[i]+1); cout<<res; return 0; }
最新回复(0)