Description
花匠栋栋种了一排花，每株花都有自己的高度。花儿越长越大，也越来越挤。栋栋决定把这排中的一部分花移走，将剩下的留在原地，使得剩下的花能有空间长大，同时，栋栋希望剩下的花排列得比较别致。
具体而言，栋栋的花的高度可以看成一列整数h1, h2, … , hn。设当一部分花被移走后，剩下的花的高度依次为g1, g2, … , gm，则栋栋希望下面两个条件中至少有一个满足：
条件 A：对于所有的1 ≤ i < m / 2，g_2i ＞ g_2i−1，且g_2i ＞ g_2i+1；
条件 B：对于所有的1 ≤ i < m / 2，g_2i ＜ g_2i−1，且g_2i ＜ g_2i+1。
此处2i及2i-1，2i+1都为下标。
注意上面两个条件在m = 1时同时满足，当m ＞ 1时最多有一个能满足。
请问，栋栋最多能将多少株花留在原地。
Input
输入的第一行包含一个整数 n，表示开始时花的株数。
第二行包含 n 个整数，依次为h1, h2,… , hn，表示每株花的高度。
Output
输出一行，包含一个整数 m，表示最多能留在原地的花的株数。
Sample Input
5
5 3 2 1 2
Sample Output
3
Hint
对于 20%的数据，n ≤ 10；
对于 30%的数据，n ≤ 25；
对于 70%的数据，n ≤ 1000，0 ≤ hi ≤ 1000；
对于 100%的数据，1 ≤ n ≤ 100,000，0 ≤ hi ≤ 1,000,000，所有的h_i随机生成，所有随机数服从某区间内的均匀分布。
题解：
推荐做这道题之前先学会LST的nlogn做法，好了，对于这道题我设了一个状态dp[i][0]表示以a[i]结尾的最长满足条件A的序列长度，dp[i][1]就是以a[i]结尾满足条件b的最长长度，很明显我们可以n平方求出dp[1~n],然后取个max就可以了，转移情况讨论就行了，比如dp[i][0]从前面的dp[j][0]的长度为基数，并且a[j]<a[i]转移，加个1取max，分四种情况就可以了，剩下的自己思考一下。优化就用两颗线段树，分别维护dp[i][0~1]为基数，偶数的情况就nlogn求出来了。
代码：
#include<iostream> #include<stdio.h> #include<stdlib.h> #include<algorithm> #include<cstring> #define inf (1<<30) const int MAXN=100100; using namespace std; int dp[MAXN][2],a[MAXN],n,ans=0,shang=0,xvv=0; struct tree{ int l,r,max; }b[1000010*4][2]; void cl(){ memset(dp,0,sizeof(dp)); memset(a,0,sizeof(a)); } void build(int xv,int l,int r){ xvv=max(xvv,xv); if(l==r){ b[xv][0].l=l,b[xv][0].r=r,b[xv][0].max=0; b[xv][1].l=l,b[xv][1].r=r,b[xv][1].max=0; return; } b[xv][0].l=l,b[xv][0].r=r,b[xv][0].max=0; b[xv][1].l=l,b[xv][1].r=r,b[xv][1].max=0; int mid=(l+r)/2; build(xv*2,l,mid); build(xv*2+1,mid+1,r); } void insert(int xv,int aum,int zhi,int x){ int l=b[xv][x].l,r=b[xv][x].r,mid=(l+r)/2; if(l==r&&r==aum){ b[xv][x].max=zhi; return; } if(aum<=mid) insert(xv*2,aum,zhi,x); else insert(xv*2+1,aum,zhi,x); b[xv][x].max=max(b[xv*2][x].max,b[xv*2+1][x].max); } int query(int xv,int l,int r,int x){ int L=b[xv][x].l,R=b[xv][x].r,mid=(L+R)/2; if(L==l&&R==r) return b[xv][x].max; if(r<=mid) return query(xv*2,l,r,x); else if(l>mid) return query(xv*2+1,l,r,x); else return max(query(xv*2,l,mid,x),query(xv*2+1,mid+1,r,x)); } void DP(){ dp[1][0]=dp[1][1]=1; insert(1,a[1],dp[1][0],1); for(int i=1;i<=n;i++){ if(a[i]!=0){ int x=query(1,0,a[i]-1,1); dp[i][0]=max(dp[i][0],x+1); } int xx=query(1,a[i]+1,shang,0); dp[i][0]=max(dp[i][0],xx+1); if(dp[i][0]%2==0) insert(1,a[i],dp[i][0],0); else insert(1,a[i],dp[i][0],1); } for(int i=1;i<xvv;i++) b[i][0].max=0,b[i][1].max=0; insert(1,a[1],dp[1][1],1); for(int i=1;i<=n;i++){ int x=query(1,a[i]+1,shang,1); dp[i][1]=max(dp[i][1],x+1); if(a[i]!=0){ int xx=query(1,0,a[i]-1,0); dp[i][1]=max(dp[i][1],xx+1); } if(dp[i][1]%2==0) insert(1,a[i],dp[i][1],0); else insert(1,a[i],dp[i][1],1); } } int main(){ cl(); scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%d",&a[i]),shang=max(shang,a[i]); shang++; build(1,0,shang); DP(); for(int i=1;i<=n;i++) ans=max(ans,dp[i][0]); for(int i=1;i<=n;i++) ans=max(ans,dp[i][1]); printf("%d",ans); }