传送门:http://acm.hdu.edu.cn/showproblem.php?pid=6880

题目大意：

对于任何一个排列，可以生成b数组来表示序列的变化情况。    

                                                 

现在给你一个b序列。问你有多少种排列符合上述b数组的限制。 (n <= 5000)

思路:

考虑dp.现在最大的问题是无法解决排列的后效性。

当我们从dp(i - 1 , ?) => dp(i , j) 的过程中。实质上可以看作要：

将 1 ~ i - 1 中的 j 置换出来到最后一个位置，且将 1 ~ i - 1 个位置中 插入一个数 i . 且依然符合b数组对排列的限制.

解决方法：将前 1 ~ i - 1 个数中的 >= j 的数统统 + 1 . 这样使得 i - 1 => i . 空出来一个j.且限制不变.

转移就很显然了. 注意dp含义以及前缀和优化,