Description
Solution
神仙DP。
设(f[i][j])是(1 - i)开头为(j)的波动序列且(j)为波峰的个数，我们考虑第二个数字，如果不是(j-1)，那么交换(j)和(j-1)还是一个波动序列，且一一对应；如果是(j-1)，那么剩下的部分是一个值域为([1,j-1]cup[j+1,i])的波动序列，离散化一下就是([1,i-1])的波动序列，然后我们再把离散化之后的序列的([j, i-1])那部分都加上(1)，再在最前面放上一个(j)，又构成了一个([1,i-1])开头为(j-1)的且(j-1)为波谷的序列和这个序列的一一对应。然后把每个数字都取个反就成了波峰了，所以就有转移：(f[i][j] = f[i][j-1]+f[i-1][i-j+1])