ZOJ2898 搜索优化

发表于 分类于

这题暴力复杂度是 O(2n)O(2^n) 的，对于 2424 的复杂度明显不可做，我的方法是进行优化，枚举前 n2\frac{n}{2} 个，得到每个陷阱对应的宝物编号，这样对应了一个映射，然后枚举剩下的宝物，找到对应陷阱所对应的前半部分宝物，所有宝物的价值之和就是目前的答案，取最大的即可。

宝物和陷阱可以用 int 和 long long 压缩，最后放入 map 中。复杂度 O(2n2)O(2^{\frac{n}{2}})

我的代码：

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
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <map>
#include <vector>

using namespace std;

vector<int> trap[25];
int v[25];
int n, maxd;
map<long long, vector<int> > mp;
int ret;

void run(int st, long long val) {
  int ans, nst;
  vector<int> part;
  if (mp.find(val) == mp.end()) return;
  part = mp[val];
  int m = part.size();
  for (int k = 0; k < m; k++) {
    nst = st | part[k];
    ans = 0;
    for (int i = 0; i < n; i++) {
      if (nst & (1 << i)) {
        ans += v[i];
      }
    }
    if (ans > ret) ret = ans;
  }
}

void dfs(int k, int st, long long val) {
  int nst;
  long long nval;
  if (k == maxd) {
    if (mp.find(val) == mp.end()) {
      vector<int> v;
      v.push_back(st);
      mp[val] = v;
    } else {
      mp[val].push_back(st);
    }
    return;
  }
  int m = trap[k].size();
  dfs(k + 1, st, val);
  nst = st;
  nval = 0;
  nst |= (1 << k);
  for (int i = 0; i < m; i++) {
    nval |= (1ll << trap[k][i]);
  }
  dfs(k + 1, nst, val ^ nval);
}

void dfs2(int k, int st, long long val) {
  int nst;
  long long nval;
  if (k == n) {
    run(st, val);
    return;
  }
  int m = trap[k].size();
  dfs2(k + 1, st, val);
  nst = st;
  nval = 0;
  nst |= (1 << k);
  for (int i = 0; i < m; i++) {
    nval |= (1ll << trap[k][i]);
  }
  dfs2(k + 1, nst, val ^ nval);
}

int main() {
  int m, x;
  while (~scanf("%d", &n)) {
    mp.clear();
    ret = 0;
    for (int i = 0; i < n; i++) {
      trap[i].clear();
      scanf("%d%d", &v[i], &m);
      for (int j = 0; j < m; j++) {
        scanf("%d", &x);
        trap[i].push_back(x);
      }
    }
    maxd = n / 2;
    dfs(0, 0, 0ll);
    dfs2(maxd, 0, 0ll);
    printf("%d\n", ret);
  }
  return 0;
}