XXI Open Cup, Grand Prix of Belarus D.Bank Security Unification

长度为 $n$ 的序列 $f_n$, 从中选出若干个数, 不改变其相对顺序, 使得 $\sum\limits_{j=1}^{k-1} f_{i_j}\&f_{i_{j+1}}$ 最大. $2 \ne n \le 10^6, 0 \le f_i \le 10^{12}$.

首先很容易想到一个 $O(n^2)$ 的 dp: 设 $dp(i)$ 为前 $i$ 个中, 选的最后一个为 $i$, 能得到的最大值. 方程为 $dp(i) = \max\limits_{1 \le j < i} \{dp(j) + (f_i \& f_j)\}$. 但很显然 $O(n^2)$ 是过不了的. 并且这范围好像用个数据结构维护起来都可能 T. 这里有个位运算. 所以一个方向是按位考虑.

我们看这个方程实际上是在干什么, 他就是一个很简单的枚举. 然后我们看一般的动态规划优化是在干什么, 他是将一些一定不是可能的最优解排除掉, 不去枚举他, 而是枚举一定可能是最优解的决策点. 那么我们需要做的就是从这个方向去考虑. 结合位运算, 那么一个方向就是, 考虑每一个位, 能不能排除一些一定不是最优的解.

由于 $f_i$ 对 $dp(i)$ 多出来的贡献是每一位是 $1$ 的个数, 那么我们可以枚举第几位, 考虑"这一位是1"的所有决策. 把这些决策单独拎出来, 一定会从离 $i$ 最近的点 $k$ ($k < i$) 转移过来, 否则假设从 $l$ ($l < k$) 转移过来, 那么如果把 $k$ 加进去, 答案会更优, 因为这一位的贡献是一样的, 但是由于 dp 值是递增的, 所以从 $k$ 转移会更好. 然后考虑"这一位是0"的所有决策, 也是同理. 那么我们把每一位都这样考虑掉, 实际上就是减少了很多不必要的枚举量, 从而使复杂度降下来.

通过这题, 可以发现 dp 优化的本质, 这也是我一直以来没有掌握的东西. 如果我们从另一个角度, 另一个方面去做"枚举", 注意依然是枚举, 只不过是换一个分类, 换一个顺序. 从这个角度去考虑"不优"的决策点, 就可以做到优化. 或者可以从题目本身的性质去想, 比如发掘单调性. 但是我太菜了, 即使能够发现性质, 也不知道怎么放在 dp 中去优化(jyz的思维就是这个, 所以jyz很强我很菜). 所以还是先从思考方向去入手叭.

然后注意 & 运算优先级问题, 和左移右移的数字, 超过 int 的要用 LL 的数字, 如 1ll << 1.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

int T, n, last[MAXN][2];
LL f[MAXN], dp[MAXN];

int main() {
  scanf("%d", &n);
  for (int i = 1; i <= n; i++)
    scanf("%lld", f + i);
  LL ans = 0;
  for (int i = 1; i <= n; i++) {
    for (int j = 0; j < 40; j++)
      for (int k = 0; k < 2; k++)
        dp[i] = max(dp[i], dp[last[j][k]] + (f[i] & f[last[j][k]]));
    for (int j = 0; j < 40; j++)
      last[j][(f[i] & (1ll << j)) > 0] = i;
    ans = max(ans, dp[i]);
  }
  printf("%lld\n", ans);
  return 0;
}