题意：
给定一个n，询问有多少种1~n的排列，使得对于任意的一个位置上的数i，相邻位置上的数都比它大，或者都比它小。（两边位置只有一个相邻的位置）
题解：
这个题目实际上是POJ1037 的简单版。lyd书上有，还看过，做过，但是就tmd忘了（或者根本没有理解）
（看到的第一反应就是这个题目，但是立刻否决了。因为题目也记不清了。而且就算想下去估计也想不起来）
DP无疑。
先想到：f[i][j]表示，前i个数，最后一个数是j的方案数。但是，第i+1个数也可以放在前i个位置。
这就考虑不到了。
于是开始打表，推规律，无果。
于是根据表开始DP，理性分析：设f[i]表示，i个排列的合法解。
推1.5h，发现和i-1非法解有关，而i-1的非法解中的转移还不一样。还得往后推。。。。。
感叹了一句：“子子孙孙无穷匮也~~~”
然后看题解。找了找lyd的书。。。
正解：
定义：一个数比相邻的数都大，叫高位。反之叫低位。
设f[i][j][0/1]表示，用i个大小不同的数，填前i个位置，最后一个数，从小到大排在第j位，并且处于（0低位）（1高位）的方案数。
然后转移：
f[i][j][0]=f[i-1][p][1] (j<=p<=i-1)
f[i][j][1]=f[i-1][p][0] (1<=p<=j-1)
如果在i中排在第j位，一定比i-1中排在第j位的数小。（反证一下）
反之，i中j位数，一定比i-1中j-1位数大。
为什么转移是对的？？？
注意，i表示i个大小不同的数，j是相对的第j位，并不是绝对的。
这样设状态是因为，i个大小不同的数，无论是什么数，对于最后一位是j名，处于0/1位的情况，方案数都是一定的。（类似离散化思想。1,2,3,4 和100,200,300,400方案一样）
我们在第i位枚举的j，其实就是相当于枚举1~i中的j。
具体的变化是这样的：
假如到了i=5，j=3，0,其实就是把3放在最左边。对于从f[4][3][1]转移，后者有一种情况是：3,1,4,2, 那么，其实进行后序列是：3,4,1,5,2
所以，对于i位取了3，把之前的3换出来，剩下1,2,4,5，和1,2,3,4放置的方法种类数相同。所以可以直接转移。
就相当于进行了一次具体数值意义下的转移。
所以转移就是对的。
代码就不写了。没有难度了。
总结：
漂亮的思维题。
主要是在设置状态的时候，用离散化的思想，抓住了i个数排列的方式都是一样的。
就是说，是几不是几，题目无所谓，我们也不关心。我们需要的时候，相当于让它是几就是几。
这种“相对”设法，还要多思考，多总结。
upda：2019.3.5:
更确切地讲，其实我们做的，是往一个球的编号为1~i-1序列里（其中i-1号球放在从下到上的第j个位置），插入编号为i的球。
这样最后形成的n个球的序列，从下往上从1~n确定数字，根据球的编号还原原来的序列，和最终的1~n的合法排列是一一对应的~！
类似的还有：
CZA、排座位、放书等等问题，这些问题是直接考虑一段一段形成然后拼接。本质是相对位置。（即我知道编号但是不关心实际位置）
本题看似是从左往右DP，但是本质还是相对顺序的记录和把球插入。
我们途中不知道也不关心到底这个球最终是哪个数字，只关心相对大小，最后填完了自然会确立。（即我知道相对位置但是不关心实际大小）
换句话说，排列有两种表示：给定n个数字、给定n-1个小于号
保留实际位置还是保留实际大小，看哪个更不容易处理就保留哪一个了。