UVA 11795 - Mega Man's Mission(状态压缩dp)(二)

Sample Input

Sample Output

3

1

1

1

2

11

01

10

3

110

011

100

000

Case 1: 1

Case 2: 2

Case 3: 3

题意：给定n代表n个敌人，第一是洛克人的武器，以下n行是n个敌人有的武器，消灭敌人后可以得到她的武器，武器的表示方式是一个二进制数能消灭敌人是1，不能是0，问总共有几种顺序可以消灭所有敌人。

思路：明显的状态压缩DP，先预处理消灭的一些敌人之后拥有的武器可以消灭的敌人数组have，然后dp，dp[i]表示消灭i这个状态的敌人有几种方法，那么推出转移方程为dp[i] = dp[i^(1<

代码：

#include 
  
   
#include 
   
     const int N = 17; const int MAXN = (1<