LibreOJ 2111 「JLOI2015」战争调度

发表于 | 分类于

Description

有一棵高\(n\)的完全二叉树，每个点可以染成黑色或者白色，黑叶子最多有\(m\)个。

如果一个叶子\(i\)和他的第\(j\)级别祖先都是黑的，那么会有一个\(w_{i, j}\)的收益。若都是白色，则有\(f_{i, j}\)的收益。求最大收益。

\(1\leq n\leq 10, m\leq 2^{n - 1}, 0\leq w_{i, j}, f_{i, j}\leq 2000\)。

Solution

如果说是在祖先上状压记录叶子的信息的话，那么状态会炸。那么我们反过来，去状压记录祖先的信息。

定义状态\(d_{i, j, s}\)表示子树\(i\)的祖宗的状态为\(s\)，子树内黑叶子有\(j\)个的最优解。转移的话在叶子上考虑\(s\)的贡献，非叶子结点背包即可。

那问题来了，这样的话时间空间不会炸吗？

先说空间。注意到\(j\)一定是某个叶子给上面的点做了贡献而成，一个叶子的贡献是\(\sum_{i = 1}^{n - 1} 2^{i - 1}\)，也就是\(2^{n - 1}\)，叶子有\(2^{n - 1}\)个，所以总的来说空间复杂度是一个\(2^{2n - 2}=O(2^{2n})\)的。

再说时间。考虑对于一个第\(i\)层的点，所有\(j\)的背包的枚举的复杂度的和的上限为\((2^{n - i})^2 = 2^{2n - 2i}\)，然后这一层不考虑\(j\)的状态数为\(2^{i - 1}2^{i - 1}\)（还不到这个数……），因此可以认为这一层对时间复杂度的贡献为\(O(2^{2n})\)，总共\(n\)层所以总时间复杂度为\(O(n2^{2n})\)。

Code

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
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cassert>
#include <algorithm>
#include <functional>
#include <utility>
#include <unordered_map>
const int maxn = 15;
const int maxno = 1030;
int siz[maxno]; int n;
void dfs(int x) {
  if(x >= (1 << (n - 1))) {
    siz[x] = 1; return;
  }
  dfs(x << 1); dfs(x << 1 | 1);
  siz[x] += siz[x << 1];
  siz[x] += siz[x << 1 | 1];
}

int w[maxno][maxn], f[maxno][maxn];
std::unordered_map<int, int> d[maxno][maxno];
int dp(int i, int j, int s) {
  if(d[i][j].count(s)) return d[i][j][s];
  int ans = 0;
  if(i >= (1 << (n - 1))) {
    assert(j == 1 || j == 0);
    int ns = s;
    for(int k = 1; k <= n - 1; k ++) {
      if(j == 1 && (ns % 2 == 1)) {
        ans += w[i][k];
      } else if(j == 0 && (ns % 2 == 0)) {
        ans += f[i][k];
      }
      ns /= 2;
    }
  } else {
    int s1 = s << 1, s2 = s << 1 | 1;
    for(int k = std::max(0, j - siz[i << 1 | 1]); k <= std::min(j, siz[i << 1]); k ++) {
      ans = std::max(ans, dp(i << 1, k, s1) + dp(i << 1 | 1, j - k, s1));
      ans = std::max(ans, dp(i << 1, k, s2) + dp(i << 1 | 1, j - k, s2));
    }
  }
  d[i][j][s] = ans;
  return ans;
}

int main() {
  int m; scanf("%d%d", &n, &m);
  for(int i = (1 << (n - 1)); i < (1 << n); i ++) {
    for(int j = 1; j <= n - 1; j ++) {
      scanf("%d", &w[i][j]);
    }
  }
  for(int i = (1 << (n - 1)); i < (1 << n); i ++) {
    for(int j = 1; j <= n - 1; j ++) {
      scanf("%d", &f[i][j]);
    }
  }
  dfs(1);
  int ans = 0;
  for(int i = m; i >= 0; i --) {
    ans = std::max(ans, dp(1, i, 0));
  }
  printf("%d\n", ans);
  return 0;
}