设f1[i]表示以1..i中某个合法序列的长度,而且最后一位是较大的
f2[i]表示以1..i中某个合法序列的长度,而且最后一位是较小的
那么就有$f1[i]=max\{f2[j]+1\},(j<i,h[j]<h[i])$,f2同理
本来想直接建线段树来维护这个最大值的,但是似乎不需要:
对于f1,如果h[i-1]<h[i],那显然从i-1更新过来比较好;但如果h[i-1]>h[i],那其实f[i]=f[i-1],因为这种情况中选i-1一定是比i不亏的,因为i-1更大一点。
f2同理
#include<bits/stdc++.h>
#define pa pair<int,int>
#define ll long long
using namespace std;
const int maxn=; inline ll rd(){
ll x=;char c=getchar();int neg=;
while(c<''||c>''){if(c=='-') neg=-;c=getchar();}
while(c>=''&&c<='') x=x*+c-'',c=getchar();
return x*neg;
} int N,h[maxn];
int f1[maxn],f2[maxn]; int main(){
int i,j,k;
N=rd();
for(i=;i<=N;i++) h[i]=rd();
f1[]=f2[]=;
for(i=;i<=N;i++){
if(h[i]>=h[i-]) f1[i]=f1[i-];
else f1[i]=f2[i-]+;
if(h[i]<=h[i-]) f2[i]=f2[i-];
else f2[i]=f1[i-]+;
}
printf("%d\n",max(f1[N],f2[N]));
return ;
}