uva11795

这题说的是一个人要消灭 所有的机器人，但是他有他可以消灭的机器人，他可以通过它消灭的机器人的武器去消灭其他的机器人， 给了一个可以消灭的关系的矩阵，计算消灭这些机器人的顺序的不同方案是多少种 ， 刚开始以为是方案数 而不是 消灭的顺序wa

我们可以知道dp[S] 这个集合的状态可以从 他的子集来， 枚举他的子集，这样可以从不同的子集来，这样我们每个点子被算一次

首先 要处理每个子集所能 到达的点的情况列举出来 ， 进行预处理，得到答案

#include <cstdio>

#include <algorithm>

#include <vector>

#include <string.h>

#include <queue>

using namespace std;

typedef long long ll;

const int maxn=;

int mto[maxn];

ll dp[<<];

char s1[maxn];

int P[<<];

int main(){

    int cas;

    scanf("%d",&cas);

    for(int cc=; cc<=cas; ++cc){

          int n;

          scanf("%d",&n);

          for(int i=; i<=n ; ++i){

               scanf("%s",s1);

               mto[i]=;

               for(int j=; j<n; ++j)

                     if(s1[j]=='')

                        mto[i]|=(<<j);

          }

          for(int S=;S<(<<n) ;++S){

               P[S]=mto[];

               for(int i=; i<n; ++i)

                 if(S&(<<i))

                    P[S]=P[S]|mto[i+];

          }

          memset(dp,,sizeof(dp));

          dp[]=;

          for(int S=; S<(<<n); ++S){

               for(int i=; i<n; ++i)

               if( ( S&(<<i) ) &&( P[S^(<<i)]&(<<i) ) ){

                   dp[S]+= dp[S^(<<i)];

               }

          }

          printf("Case %d: %lld\n",cc,dp[(<<n)-]);

    }

    return ;

}