[HDOJ3664 Permutation Counting]【递推】

【题目链接】http://acm.hdu.edu.cn/showproblem.php?pid=3664

【题目大意】

输入n和k。

输出n的所有排列里有多少个是Ai>i的数量等于k的。

【算法分析】

递推。

F[n,k]表示对应答案。

然后F[n,k]=F[n-1,k]*(k+1)+F[n-1,k-1]*((n-1) – (k-1))

本质是现在多一个数字n,也多了一个位置An。

从F[n-1,k]那里继承过来的是用n去填那些已经满足Ai>i的位置,因为现在n是最大的,所以填进去以后肯定也是满足Ai>i的,然后原本对应位置的数字就填到An上。因为可以填本身An这个位置,所以系数+1。

从F[n-1,k-1]那里继承过来的是用n去和前面那些满足Ai<=i的位置上的数交换,因为现在n是最大的,所以填了以后显然满足Ai>i。

【Hint】

必须打表才能过。

【CODE】

http://xiudaima.appspot.com/code/detail/4344003

留下评论

您的电子邮箱地址不会被公开。 必填项已用 * 标注