NOIP 模拟 $30\; \rm 毛二琛$

题解 \(by\;zj\varphi\)

原题问的就是对于一个序列,其中有的数之间有大小关系限制,问有多少种方案。

设 \(dp_{i,j}\) 表示在前 \(i\) 个数中,第 \(i\) 个的排名为 \(j\)的方案数

方程:

\[f_{i,j}=\begin{cases} \sum\limits_{k=j}^{i-1} f_{i-1,k},(p_{i-1}<p_i)\\ \sum\limits_{k=1}^{j-1} f_{i-1,k},(p_{i-1}>p_i)\\ \end{cases} \]

直接前缀和优化即可 \(\mathcal O\rm(n^2)\)

上一篇:RelativeLayout相对布局


下一篇:b_zj_小于左边且大于右边的所有数(单调栈)