$\text{蒟蒻在DP之路上求索着}$

题面:P2401 不等数列

平时在写DP的时候不能看到题目就开始想状态.应该先看题目能不能提取出什么有利于解决的信息或者能不能转化成更简单的问题.还有很重要的一点是,可以不从头考虑问题,而是假设前面已经推出了答案,然后考虑下一步.在这个题目中,我们比较容易找到子问题,设$f[i][j]$表示在一个$1…i$的排列中有恰好有$j$个小于号的时候的个数.那么如果我们现在已经推出了$i-1$个数的答案,现在考虑把第i个数排在哪里.

  1. 放在序列最左边,大于号++,小于号不变
  2. 放在序列最右边,小于号不变,小于号++
  3. 插入左边小右边大(也就是原本一个小于号)的位置,大于号++,小于号不变
  4. 插入左边大右边小(也就是原本一个大于号)的位置,大于号不变,小于号++

由以上规律我们可以发现,如果我们得到了$f[i][j]$,我们通过它能更新$f[i+1][j]$和$f[i+1][j+1]$(因为小于号要么不变要么变多).其中有$j+1$个位置可以使小于号不变,有$i-j$个位置可以使小于号增加.所以我们得出了以下的转移方程:
$$
f[i+1][j]=(j+1)\times f[i][j]\f[i+1][j+1]=(i-j)\times f[i][j]
$$
初始化$f[1][0]=1$,这个问题就解决了

——Gensokyo