任性乌龟

文章
4
资源
0
加入时间
2年10月21天

uva 11795(状态压缩dp)

题意:有一个机器人要杀死其他n(1 <= n <= 16)个机器人,他自己配备了一个武器,并且给出了这个武器能杀死的敌人,如101表示他能杀死第1和第3个敌人,这样他就能得到第1和第3号敌人的武器,从而杀死更多的敌人,问他杀死所有的敌人的方法数。 题解:因为敌人数最多是16个,很容易想到应该是状态压缩dp,可以用f[S]表示状态S下进制位为1的敌人全被杀死的方案数,那么结果就是f[(1 << n)