UVA 11795 Mega Man's Mission -

题目地址：http://vjudge.net/problem/UVA-11795

如果 原来的枪不会掉的话，那么首先先杀谁都没什么关系了

d[i] 表示杀了i状态的人 ， 从i状态出发，杀了所有人 ，有几种方法

很简单题，结果 调试半天 ..  状态好烂

#include <bits/stdc++.h> using namespace std; #define REP(i,a,b) for(int i=a;i<=(int)(b);++i) #define REPD(i,a,b) for(int i=a;i>=(int)(b);--i) const int maxn=1<<17; typedef long long LL; LL d[maxn]; int a[18],n,MB; char s[18]; int getGun(int state){ //state 表示那些人killed int gun=MB; REP(i,0,n-1) if((1<<i)&state) gun|=a[i]; return gun; } LL DP(int state){ LL& ans=d[state]; if(ans!=-1) return ans; int gun=getGun(state); ans=0; REP(i,0,n-1) if(gun&(1<<i)&&!(state&(1<<i))) ans+=DP(state+(1<<i)); //kill i return ans; } int main(int argc, char const *argv[]) { int T,kase=0; scanf("%d",&T); while(T--&&scanf("%d",&n)==1) { scanf("%s",s); MB=0; REP(i,0,n-1) if(s[i]=='1') MB|=(1<<i); REP(i,0,n-1) { scanf("%s",s); a[i]=0; REP(j,0,n-1) if(s[j]=='1') a[i]|=(1<<j); } int ALL=(1<<n)-1; memset(d,-1,sizeof(d)); d[ALL]=1; printf("Case %d: %lld\n", ++kase,DP(0)); } return 0; }