首页 > 代码库 > uva
uva
这题说的是一个人要消灭 所有的机器人，但是他有他可以消灭的机器人，他可以通过它消灭的机器人的武器去消灭其他的机器人， 给了一个可以消灭的关系的矩阵，计算消灭这些机器人的顺序的不同方案是多少种 ， 刚开始以为是方案数 而不是 消灭的顺序wa
我们可以知道dp[S] 这个集合的状态可以从 他的子集来， 枚举他的子集，这样可以从不同的子集来，这样我们每个点子被算一次
首先 要处理每个子集所能 到达的点的情况列举出来 ， 进行预处理，得到答案
#include <cstdio>#include <algorithm>#include <vector>#include <string.h>#include <queue>using namespace std;typedef long long ll;const int maxn=20;int mto[maxn];ll dp[1<<16];char s1[maxn];int P[1<<16];int main(){ int cas; scanf("%d",&cas); for(int cc=1; cc<=cas; ++cc){ int n; scanf("%d",&n); for(int i=0; i<=n ; ++i){ scanf("%s",s1); mto[i]=0; for(int j=0; j<n; ++j) if(s1[j]==‘1‘) mto[i]|=(1<<j); } for(int S=0;S<(1<<n) ;++S){ P[S]=mto[0]; for(int i=0; i<n; ++i) if(S&(1<<i)) P[S]=P[S]|mto[i+1]; } memset(dp,0,sizeof(dp)); dp[0]=1; for(int S=0; S<(1<<n); ++S){ for(int i=0; i<n; ++i) if( ( S&(1<<i) ) &&( P[S^(1<<i)]&(1<<i) ) ){ dp[S]+= dp[S^(1<<i)]; } } printf("Case %d: %lld\n",cc,dp[(1<<n)-1]); } return 0;}
uva
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。