巧妙计数dp-Permutation Counting
传送门: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含义以及前缀和优化,
安克创新 Anker公司福利 743人发布