当前位置:首页 > 动态规划 > 状压DP > 正文
SSOJ1345组合数的输出
283+

题目大意:找出从自然数1、2、… 、n(0<n<10)中任取r(0<r<=n)个数的所有组合。

输入

输入n、r。

输出

按特定顺序输出所有组合,特定顺序:每一个组合中的值从大到小排列,组合之间按逆字典序排列。

样例输入

5 3

样例输出

543
542
541
532
531
521
432
431
421
321

解题思路

这里用状态压缩、位运算以及枚举来解决。

n小于10,每个要么选,要么不选,1代表选,0代表不选,那么所有组合共有2^n种,枚举每一种状态,不会超时;如状态101,表示第1、3个数要选、要输出;对于每一个状态,逐位判断是否有1,有1的话,就输出该位代表的数字(或字符),如果第j位是1,那么状态i & 1<<j-1为1;当然,题目要求r个数的组合,即状态中1的个数是r才行,我们可以预处理每个状态1的个数,或者写个求1的个数的函数。

程序实现

更多

About

坚决不Copy代码!

本文标签:,,,,,

SSOJ1345组合数的输出:等您坐沙发呢!

发表评论

😉😐😡😈🙂😯🙁🙄😛😳😮mrgreen.png😆💡😀👿😥😎😕

快捷键:Ctrl+Enter