题意:
你最初只有一个武器,你需要按照一定的顺序消灭n个机器人(n<=16)。每消灭一个机器人将会得到他的武器。每个武器只能杀死特定的机器人。问可以消灭所有机器人的顺序方案总数。
分析:
基础的集合dp,我是用f[s][num]表示已经得到武器状态s,已经杀了num个机器人后可以得到的方案总数,然后dfs一下就好,比较简单。
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
typedef long long ll;
const int INF = 0x3f3f3f3f;
const int N = 17;
int vis[N], n, a[N];
long long fac[N], f[1 << N][N];
bool flag[1 << N][N];
int ALL; //(1<<n)-1
/*
f[s][num]表示已经得到武器s,已经杀了num个机器人后可以得到的顺序总数
那么如果s==ALL,就说明已经得到所有武器,那么剩下的n-num个人就可以随便杀了(方案数是n-num的全排列)
所以dfs一下就好
*/
ll dfs (int st, int num) {if (st != ALL && num >= n) return 0;if (flag[st][num]) return f[st][num];flag[st][num] = 1;ll& ans = f[st][num];if (st == ALL) {ans = fac[n - num];return ans;}for (int i = 0; i < n; i++) {if (!vis[i] && (st & (1 << i) ) ) {vis[i] = 1;ans += dfs (st | a[i], num + 1);vis[i] = 0; //回溯,可以先不杀这个,先杀其它的}}return ans;
}
int main() {//freopen("f.txt","r",stdin);int T;fac[0] = 1;for (int i = 1; i <= 16; i++) fac[i] = fac[i - 1] * i; //fac[i]保存i的全排列scanf ("%d", &T);for (int cas = 1; cas <= T; cas++) {scanf ("%d", &n );memset (vis, 0, sizeof (vis) );memset (flag, 0, sizeof (flag) );memset (f, 0, sizeof (f) );int st = 0, x;for (int j = 0; j < n; j++) {scanf ("%1d", &x);if (x) st |= (1 << j);}for (int i = 0; i < n; i++) {a[i] = 0;for (int j = 0; j < n; j++) {scanf ("%1d", &x);if (x) a[i] |= (1 << j);}}ALL = (1 << n) - 1;printf ("Case %d: %lld\n", cas, dfs (st, 0) );}return 0;
}
看了别人的想法写的,感觉不错~~
#include<iostream>
#include<cstring>
#include<vector>
#include<cstdio>
using namespace std;
typedef long long ll;
const int INF = 0x3f3f3f3f;
const int N = 17;
int n, a[N];
long long f[1 << N], dp[1 << N];
int ALL;
/*
f[s]表示得到状态是s的武器后,可以转移到的状态(也就是还可以杀哪个机器人)
dp[s]表示得到状态s的总方案数
*/
int main() {//freopen("f.txt","r",stdin);int T;scanf ("%d", &T);for (int cas = 1; cas <= T; cas++) {scanf ("%d", &n );memset (f, 0, sizeof (f) );int st = 0, x;for (int j = 0; j < n; j++) {scanf ("%1d", &x);if (x) st |= (1 << j);}for (int i = 0; i < n; i++) {a[i] = 0;for (int j = 0; j < n; j++) {scanf ("%1d", &x);if (x) a[i] |= (1 << j);}}ALL = (1 << n) - 1;for(int s = 0; s <= ALL; s++) {f[s] = st;for(int i = 0; i < n; i++)if(s & (1 << i))f[s] |= a[i]; //统计s状态可以转移到f[s]状态}dp[0] = 1;for(int s = 1; s <= ALL; s++) {dp[s] = 0;for(int i = 0; i < n; i++)if((s & (1 << i)) && (f[s ^ (1 << i)] & (1 << i)))//[s ^ (1 << i)状态通过杀掉第i个机器人可以得到s这个状态dp[s] += dp[s ^ (1 << i)]; //那么判断是否可以杀掉i的前提就是f[s ^ (1 << i)]有(1 << i)//这个武器}printf ("Case %d: %lld\n", cas, dp[ALL]);}return 0;
}
/*
Input
3
1
1
1
2
11
01
10
3
110
011
100
000
Output
Case 1: 1
Case 2: 2
Case 3: 3*/