uva 11795(状态压缩dp)

60 阅读 0 评论 40 点赞

我是靠谱客的博主任性乌龟，这篇文章主要介绍uva 11795(状态压缩dp)，现在分享给大家，希望可以做个参考。

题意：有一个机器人要杀死其他n(1 <= n <= 16)个机器人，他自己配备了一个武器，并且给出了这个武器能杀死的敌人，如101表示他能杀死第1和第3个敌人，这样他就能得到第1和第3号敌人的武器，从而杀死更多的敌人，问他杀死所有的敌人的方法数。
题解：因为敌人数最多是16个，很容易想到应该是状态压缩dp，可以用f[S]表示状态S下进制位为1的敌人全被杀死的方案数，那么结果就是f[(1 << n) - 1]，如果拿掉了状态S中的杀死第j个人能得到的武器，剩下的人如果能杀死第j个人，就把这个状态的方法数加到f[S]中。

复制代码

#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
const int N = 20;
const int M = (1 << 16) + 100;
int n, w[N], s[M];
char str[N];
long long f[M];

int main() {
    int t, cas = 1;
    scanf("%d", &t);
    while (t--) {
        memset(f, 0, sizeof(f));
        scanf("%d", &n);
        int all = (1 << n) - 1;
        for (int i = 0; i < n + 1; i++) {
            scanf("%s", str);
            w[i] = 0;
            for (int j = 0; j < n; j++)
                if (str[j] == '1')
                    w[i] |= (1 << j);
        }
        //s[i]表示在状态i下杀死进制位是1的所有能杀死的人
        //f[i]表示在状态i下的能把进制位是1的杀死的方案数
        s[0] = w[0];
        for (int i = 1; i <= all; i++) {
            s[i] = w[0];
            for (int j = 0; j < n; j++)
                if ((i >> j) & 1)
                    s[i] |= w[j + 1];
        }
        f[0] = 1;
        for (int i = 1; i <= all; i++) {
            for (int j = 0; j < n; j++)
                if ((s[i ^ (1 << j)] >> j) & 1)
                    f[i] += f[i ^ (1 << j)];    
        }
        printf("Case %d: %lldn", cas++, f[all]);
    }
    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
const int N = 20;
const int M = (1 << 16) + 100;
int n, w[N], s[M];
char str[N];
long long f[M];

int main() {
    int t, cas = 1;
    scanf("%d", &t);
    while (t--) {
        memset(f, 0, sizeof(f));
        scanf("%d", &n);
        int all = (1 << n) - 1;
        for (int i = 0; i < n + 1; i++) {
            scanf("%s", str);
            w[i] = 0;
            for (int j = 0; j < n; j++)
                if (str[j] == '1')
                    w[i] |= (1 << j);
        }
        //s[i]表示在状态i下杀死进制位是1的所有能杀死的人
        //f[i]表示在状态i下的能把进制位是1的杀死的方案数
        s[0] = w[0];
        for (int i = 1; i <= all; i++) {
            s[i] = w[0];
            for (int j = 0; j < n; j++)
                if ((i >> j) & 1)
                    s[i] |= w[j + 1];
        }
        f[0] = 1;
        for (int i = 1; i <= all; i++) {
            for (int j = 0; j < n; j++)
                if ((s[i ^ (1 << j)] >> j) & 1)
                    f[i] += f[i ^ (1 << j)];    
        }
        printf("Case %d: %lldn", cas++, f[all]);
    }
    return 0;
}