f[1][1]=1;for(int i=2;i<=n;i++)    for(int j=1;j<=i;j++){    f[i][j]=f[i-1][i-j]+f[i][j-1];} ans=f[n][n]*2;

f[i][j]  i:第i位

  j:第i位是1-j情况的和

将先上升序列的任何一位x变成n-x+1，变成先下降序列。

先上升序列i位1~j，取反变成先下降序列i-j+1~i,对应先上升序列1~i-j+1；

先上升序列i-1位，对应先上升序列1~i-j+1-1->1~i-j

 

 http://blog.csdn.net/AaronGZK/article/details/44871391

将题目简化为1-n的所有排列中满足高低交替出现的个数，可以用动态规划实现。

我们用f[n][k]表示n个数，最后一个为k且最后两个递增，g[n][k]表示n个数最后一个数为k且最后两个递减。对于f[n][k]，若我们将数列中每个数x换为n+1-x，则就成了g[n][n+1-k]。

所以可得f[n][k]=g[n][n+1-k]。

那么可得：

 

所以动态转移方程为f[n][k]=f[n][k-1]+f[n-1][n-k+1]

 

由于对称性，最终的答案为2ans。

if (n==1)      {          cout<<1<