题目：codevs 3289 花匠
链接：http://codevs.cn/problem/3289/
这道题有点像最长上升序列，但这里不是上升，是最长“波浪”子序列。用动态规划可以解决，方程类似最长上升子序列：
f[i]=max(f[j]) ( 1≤j≤i-1 && ( (f[j]%2=1 && A[j]<A[i] ) || (j%2=0 && A[j]>A[i]) ) )
p[i]=max(p[i]) ( 1≤j≤i-1 && ( (p[j]%2=1 && A[j]>A[i] ) || (j%2=0 && A[j]<A[i]) ) )
结果：
ans=max(f[n],p[n])
...写出来，很恶心的方程，因为题目中是有两种情况，第一种是 第一个元素 < 第二个元素 开始的波浪序列，另一种是 第一个元素 > 第二个元素 开始的波浪序列。我这里的f[i]是第一种情况算出来的最长波浪序列，p[i]是第二种情况算出来的最长波浪序列，然后最后的答案是两者之间选一个最大的。这样用o(n²)的算法可以达成，但是注意，题目中的数据量是10,000 ，肯定时间要超，所以还是要用优化。
最长上升子序列中可以用线段树优化，那么这里怎么优化呢？
我的笨笨做法是开4个线段树：maxfj[],maxfo[],maxpj[],maxpo[]。
maxfj[]维护f[i]是奇数的最大值，maxfo[]维护f[i]是偶数的最大值。
maxpj[]维护p[i]是奇数的最大值，maxpo[]维护p[i]是偶数的最大值。
因为f[i]中，当f[i]是奇数的时候，区间是1到A[i]-1中的最大值，而当f[i]是偶数的时候，区间是A[i]+1到n的最大值（因为是严格单调，所以要+1或-1）。
当p[i]是奇数的时候，区间是A[i]+1到n的最大值，而当p[i]是偶数的时候，区间是1到A[i]-1中的最大值。
所以不能同时维护，要分开来，因此就是4个线段树。
当然，A[i]的值很大，要做离散化。
大致思路就是这样吧。
附代码：
#include<cstdio>
#include<algorithm>
#include<iostream>
using namespace std;
const int maxn=; int n,maxfj[maxn*],maxfo[maxn*],f[maxn],p[maxn],maxpj[maxn*],maxpo[maxn*]; struct u
{
int v,r;
bool operator <(const u &rhs) const
{
return v<rhs.v;
}
}A[maxn]; bool cmp(u a,u b)
{
return a.r<b.r;
} int w,v;
void updatefj(int o,int L,int R)
{
if(L==R) maxfj[o]=max(maxfj[o],v);
else
{
int M=(L+R)/;
if(w<=M) updatefj(o*,L,M); else updatefj(o*+,M+,R);
maxfj[o]=max(maxfj[o*],maxfj[o*+]);
}
} int y1,y2,ans;
void queryfj(int o,int L,int R)
{
if(y1<=L && R<=y2) ans=max(ans,maxfj[o]);
else
{
int M=(L+R)/;
if(y1<=M) queryfj(o*,L,M);
if(y2>M) queryfj(o*+,M+,R);
}
}
void updatefo(int o,int L,int R)
{
if(L==R) maxfo[o]=max(maxfo[o],v);
else
{
int M=(L+R)/;
if(w<=M) updatefo(o*,L,M); else updatefo(o*+,M+,R);
maxfo[o]=max(maxfo[o*],maxfo[o*+]);
}
} void queryfo(int o,int L,int R)
{
if(y1<=L && R<=y2) ans=max(ans,maxfo[o]);
else
{
int M=(L+R)/;
if(y1<=M) queryfo(o*,L,M);
if(y2>M) queryfo(o*+,M+,R);
}
}
void updatepj(int o,int L,int R)
{
if(L==R) maxpj[o]=max(maxpj[o],v);
else
{
int M=(L+R)/;
if(w<=M) updatepj(o*,L,M); else updatepj(o*+,M+,R);
maxpj[o]=max(maxpj[o*],maxpj[o*+]);
}
} void querypj(int o,int L,int R)
{
if(y1<=L && R<=y2) ans=max(ans,maxpj[o]);
else
{
int M=(L+R)/;
if(y1<=M) querypj(o*,L,M);
if(y2>M) querypj(o*+,M+,R);
}
} void updatepo(int o,int L,int R)
{
if(L==R) maxpo[o]=max(maxpo[o],v);
else
{
int M=(L+R)/;
if(w<=M) updatepo(o*,L,M); else updatepo(o*+,M+,R);
maxpo[o]=max(maxpo[o*],maxpo[o*+]);
}
} void querypo(int o,int L,int R)
{
if(y1<=L && R<=y2) ans=max(ans,maxpo[o]);
else
{
int M=(L+R)/;
if(y1<=M) querypo(o*,L,M);
if(y2>M) querypo(o*+,M+,R);
}
} int main()
{
cin>>n;
for(int i=;i<=n;i++) cin>>A[i].v,A[i].r=i;
//离散化
sort(A+,A+n+);
for(int i=,nw=;i<=n;i++)
{
f[i]=,p[i]=;//顺便做的f[],p[]初始化
if(A[i+].v!=A[i].v) nw++,A[i].v=nw-;
else A[i].v=nw;
}
sort(A+,A+n+,cmp); w=A[].v,v=f[];
updatefj(,,n);
updatepj(,,n); for(int i=;i<=n;i++)
{
y1=,y2=A[i].v-,ans=;
if(y2>=y1) queryfj(,,n);//注意，因为有A[i]-1，所以要判断区间的存在
y1=A[i].v+,y2=n;
if(y2>=y1) queryfo(,,n);
f[i]=ans+;
v=f[i],w=A[i].v;
if(f[i]%==) updatefj(,,n);
else updatefo(,,n); y1=,y2=A[i].v-,ans=;
if(y2>=y1) querypo(,,n);
y1=A[i].v+,y2=n;
if(y2>=y1) querypj(,,n);
p[i]=ans+;
v=p[i],w=A[i].v;
if(p[i]%==) updatepj(,,n);
else updatepo(,,n);
} cout<<max(f[n],p[n]);
return ;
}