给一个序列,如果经过k次冒泡能使其变为单增序列,则称该序列为k回合冒泡序列
现在给你n,k, 问在n的全排列中,k回合冒泡序列有多少个
这题看规模就是要推一个公式出来
discuss里的一个解法非常好,让人可以理解
对于n个元素,假设为{0,1,...n- 1},可以发现
对于任意一个排列,假设L(i) 表示位置i上的元素的前面有多少数字比它大, 那么得到了一个L序列。
那么可以知道 交换的轮数 = max{ L(i) } (0 <= i < n)
并且可以发现,对于所有n!种序列,其L序列满足:{[0,0],[0,1],[0,2]...[0,n-1] }...(1)
[a,b] 表示值在[a,b] 之......
阅读全文