UVa11795 Mega Man’s Missions

問題文
http://uva.onlinejudge.org/external/117/11795.html

概要
"Mega Man" であるあなたは "Mega Buster" を使って敵のロボットを倒していく。ただ "Mega Buster" だけでは全ての敵を倒すことが出来ない。倒した敵から武器を奪い、その武器を使うことで倒せなかった敵も倒せるようになる。敵を一体を倒す度、その敵と同じ番号の新たな武器が手に入る。どの武器でどの敵が倒せるかの表が与えられるので、全ての敵を倒す方法が何通りあるかを求めよ。

解法
ビットDPする。

dp[S] := 集合Sの武器を持っている（自分の武器を除くとS-1体倒した）状態を生む場合の数

Sの最下位ビットを "Mega Buster" とみなして、初期条件 dp[1] = 1 とした。

AOJ2254 Fastest Route と似たような問題と解法。

反省
場合の数が16!より大きくなるので、long long にする必要があった。
どの武器を使用したかに関係なく、異なる武器の集合で敵を倒した場合を数え上げていくことに注意する必要があった。（下のコード、for文中のbreakをすべき）

#include <bits/stdc++.h>

using namespace std;

typedef long long ll; // 16! より大きい

int main() {
  
  int Tc; cin >> Tc;
  for(int Tcnt=1; Tcnt<=Tc; Tcnt++) {
    int N; cin >> N;
    int G[N+1][N];
    
    for(int i=0; i<N+1; i++) {
      for(int j=0; j<N; j++) {
	char ch; cin >> ch;
	G[i][j] = ch == '1';
      }
    }
    
    int V = N+1;
    ll dp[1<<V]; memset(dp, 0, sizeof dp);
    dp[1] = 1;
    for(ll S=1; S<(1<<V)-2; S++) {
      for(int i=1; i<V; i++) {
	if((S >> i) & 1) continue;
	for(int k=0; k<V; k++) {
	  if( !((S >> k) & 1) ) continue;
	  if( !G[k][i-1] ) continue;
	  dp[S|(1<<i)] += dp[S]; // 持っている武器の集合Sでiを倒せた
	  break;
	}
      }
    }
    
    cout << "Case " << Tcnt << ": " << dp[(1<<V)-1] << endl;
    
  }
  
  return 0;
}