看到这道题第一反应就把该题与白书的一道例题联系起来了.(虽然后来证明两者并没有联系.)因此我一开始的思路就是从n到1一个个加进去.虽然的确搞不太出来.
首先可以证明.一个开头下降的抖动子序列 1~n 可以通过 n - xi + 1 (xi 为 第i位的值 )的形式变为一个上升的.
设 f[i][j] 为长度为 i , 分别以 1~j 开头且开头上升(如果你要问我为什么是上升的你可以自己推一下,反正我推不出来.)的方案数(输出时答案*2就好).
如果以 j 开头,且序列为 1~i 又因为开头要上升.所以第二位的取值范围为 j+1~i 又因为为抖动子序列. 那么第二位开始要下降. 可我们求的是下降的怎么办呢(或者说已有的表现形式是上升的)?
我们可以用一开始的性质把下降的转化成上升的.如果一开始的取值范围为 j+1 ~ i 那么通过 n - xi + 1 转化后, 开头的取值范围就变为了 1 ~ i-j. (如果之前的表示是上升的会在这里出问题.) 那么很明显就是 f[i-1][i-j] 了,至于为什么是 i-1, 因为序列的长度只有 i-1 个了.就这样.