【传送门：】

---

简要题意：

　　给出n个格子，要求每个格子的数均为1到n，且每种数字只出现一次，要求能够使这n个格子能够成为抖动数列的放置方法

　　抖动数列就是指数列中的每一个数，要么比相邻的数都小（原题表示为山谷），要么比相邻的数都大（原题表示为山峰）

---

题解：

　　毒瘤DP！！！活生生的思维两小时，代码两分钟的毒瘤题！

　　一开始想这道题就想到设f[i][j]为处理到第i个格子时，a[i]为j且使得a[i]为山峰的情况数

　　结果发现转移不了

　　听取了Hanks_o大佬的话，膜了一发题解

　　设f[i][j]为处理到第i个格子时，首位的数取值范围为1到j并且使得最后两个数递增的情况数

　　g[i][j]为处理到第i个格子时，首位的数取值范围为1到j并且使得最后两个数递减的情况数

　　那么对于f[i][j]时的所有情况的数列的每个数k都换成i-j+1的话，就相当于g[i][i-j+1]

　　所以f[i][j]=g[i][i-j+1]，g[i][j]=f[i][i-j+1]

　　∵$f[i][j]=\sum_{k=1}^{j-1}g[i-1][k]$,$g[i][j]=f[i][i-j+1]$

　　∴$g[i-1][k]=f[i-1][i-k]$

　　∴$f[i][j]=\sum_{k=1}^{j-1}f[i-1][i-k]$

　　∴$f[i][j]=\sum_{k=i-j+1}^{i-1}f[i-1][k]$

　　∴$f[i][j-1]=\sum_{k=i-j+2}^{i-1}f[i-1][k]$

　　∴$f[i][j]=f[i][j-1]+f[i-1][i-j+1]$

　　然后就可以转移啦啦啦！！

　　要滚动数组不然MLE

---

参考代码：

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          using namespace std;int f[2][5100];int main(){    int n,p;    scanf("%d%d",&n,&p);    memset(f,0,sizeof(f));    int now=0;    f[0][1]=1;    for(int i=2;i<=n;i++)    {        memset(f[now^1],0,sizeof(f[now^1]));        for(int j=1;j<=i;j++)        {            f[now^1][j]=(f[now^1][j-1]+f[now][i-j+1])%p;        }        now^=1;    }    int ans=0;    for(int j=1;j<=n;j++) ans=(ans+f[now][j])%p;    printf("%d\n",(ans*2)%p);    return 0;}