题解：
一道不错的dp
方法1：
首先会发现它的要求就是数列是摆动的
然后算法大体上是dp方向
会发现这道题对大小之间的差距并没有高的要求
比如 1,3,5与1,2,3实际是等效的
用一个套路：枚举最大值将序列分割
用f[i][0]表示上升，f[i][1]表示下降
转移的话应该挺显然的，最大值右边显然是一个上升序列，左边嘛要根据元素个数判断一下
方法2：
这个是正解。。看上去很简单，但自己想不出来啊。。
状态不难设
令f[i][j]表示取前i个数的排列，其中第一个数为j的方案数，下降
考虑转移，满满的递推思想啊。。
性质1：
对于某个排列来说，若j,j-1不相临，他们是可以互换的（虽然显然但自己想不到啊。。）
这样当f[i][j]中j与j-1不相邻的时候，就等于f[i][j-1]
性质2（其实不重要）：
就是上升变下降 g[i][j]=f[i][i-j]
对于某个排列来说，若j，j-1相邻，那么问题就变为了在i-1个元素里，第一个是j-1的上升序列
网上大都是f[i-1][i-j]。。。其实处理个g数组不是差不多么。。
另外对于初值，f[1][1]=1;其余f[i][1]=0；第一个是1还怎么下降。。