原题链接：https://www.luogu.org/problem/show?pid=1970
前几天刚做的一道DP，没想到是原题，不看标签瞎**（和谐）做系列。
用两个数组f1,f2记录两种不同的波动序列（先这么叫吧）
为什么f1[1],f2[1]可以赋值为1，难道第一盆一定选？
是的，第一盆就是必选的，举个例子。
假设a中有一个不包含a[1]的最长波动序列，b1,b2,b3...bm.假设b1<b2
A a1==b1时，用a1代替b1,答案不会变坏。
B a1<b1，用a1代替b1,答案仍然不会变坏。
C a1>b1，加入a1,答案会增加1,。
b1>b2时同理。
由此可见，a1选用，答案不会变坏，反而可能变得更好。
然后分三种情况转移。
1 h[i]==h[i-1] 此时保留h[i]或者h[i-1]都是一样的
2 h[i]<h[i-1] 此时对于两个数组来说，意义是不同的，其中一个数组，就像B情况，保留i位置或是i-1位置都是一样的，
另一个数组则是C情况，只不过要从另一个数组转移过来罢了。
3 h[i]>h[i-1] 对于两个数组来说，意义与上面相似，但是相反。
最后比较一下两个f[n],输出较大的一个。
如果不放心，可以像被注释掉的三行一样，输出两个数组中的每个数据。（开数组就是为了这么用的，不然完全可以用O（1）空间复杂度写完这个题）
#include<cstdio> void read(int &y) { y=0;char x=getchar(); while(x<'0'||x>'9') x=getchar(); while(x>='0'&&x<='9') { y=y*10+x-'0'; x=getchar(); } } int max(int x,int y) { if(x>y) return x; else return y; } int n,h[100005],f1[100005],f2[100005]; int main() { read(n); for(int i=1;i<=n;i++) read(h[i]); f1[1]=1;f2[1]=1; for(int i=2;i<=n;i++) { if(h[i]>h[i-1]) { f1[i]=max(f1[i-1],f2[i-1]+1); f2[i]=f2[i-1]; } if(h[i]==h[i-1]) { f1[i]=f1[i-1]; f2[i]=f2[i-1]; } if(h[i]<h[i-1]) { f1[i]=f1[i-1]; f2[i]=max(f2[i-1],f1[i-1]+1); } } // for(int i=1;i<=n;i++) printf("%d ",f1[i]); // printf(" "); // for(int i=1;i<=n;i++) printf("%d ",f2[i]); printf("%d",max(f1[n],f2[n])); return 0; }
丧心病狂的O（1）空间复杂度：
#include<cstdio> void read(int &y) { y=0;char x=getchar(); while(x<'0'||x>'9') x=getchar(); while(x>='0'&&x<='9') { y=y*10+x-'0'; x=getchar(); } } int max(int x,int y) { if(x>y) return x; else return y; } int n,h,f1=1,f2=1,x; int main() { read(n);read(h); for(int i=2;i<=n;i++) { x=h;read(h); if(h>x) f1=max(f1,f2+1); if(h<x) f2=max(f2,f1+1); } printf("%d",max(f1,f2)); return 0; }