资讯详情

\(\text{atcoder-arc100c}\)

SOS-dp 模板题。

首先讲一下 SOS-dp 是个什么东西，实际上就是优化子集枚举的一个算法，本质上是状压 dp。

这道题的弱化版是这样的：令 \(f_S = \sum\limits_{T \subseteq S} a_T\)，求对于所有的 \(0 \le S < 2^n\)，\(f_S\) 的值。

首先朴素算法的时间复杂度是 \(O(4^n)\) 的：

for(int S = 0; S < (1 << n); S ++)for(int T = 0; T < (1 << n); T ++) if((S & T) == T) f[S] += a[T];

朴素算法第二维枚举的时间复杂度太高了，我们只需要枚举 \(S\) 的子集。

如果 \(S\) 中有 \(k\) 个 \(1\)，那么它有 \(2^k\) 个子集，这样的 \(S\) 有 \(\binom{n}{k}\) 个，总枚举次数为 \(\sum\limits_{k=0}^n \binom{n}{k}2^k=(1+2)^n=3^n\)，用了二项式定理。所以时间复杂度就降到了 \(O(3^n)\)，具体怎么不重不漏枚举子集可以看代码：

for(int S = 0; S < (1 << n); S ++) {f[S] = a[0];for(int T = S; T; T = (T - 1) & S) f[S] += a[T];
}

但这个时间复杂度还是太高了，于是我们就要用到 SOS-dp 了，即高位前缀和。

首先考虑三维的前缀和怎么写，我们这里不用基于容斥的前缀和计算方式，用逐维前缀和。

对于一般情形，给定 \(k\) 维数组 \(a\)，大小为 \(n\)，要求其前缀和 \(S\)，有下式：

\[S_{i_1,\cdots,i_k} = \sum_{i_1' \le i_1} \cdots \sum_{i_k' \le i_k} a_{i_1',\cdots,i_k'} \]

从上式可以看出，\(k\) 维前缀和就等于 \(k\) 次求和。所以，一个显然的算法是，每次只考虑一个维度，固定所有其他维度，然后求若干个一维前缀和，这样对于 \(k\) 个维度分别求和之后，得到的就是 $k 维前缀和。

下面是一种三维前缀和的实现：

for(int i = 1; i <= n; i ++) for(int j = 1; j <= n; j ++)for(int k = 1; k <= n; k ++) s[i][j][k] += s[i][j][k - 1];
for(int i = 1; i <= n; i ++) for(int j = 1; j <= n; j ++)for(int k = 1; k <= n; k ++) s[i][j][k] += s[i][j - 1][k];
for(int i = 1; i <= n; i ++) for(int j = 1; j <= n; j ++)for(int k = 1; k <= n; k ++) s[i][j][k] += s[i - 1][j][k];

那么推广到这题的 \(n\) 维每一维只有 \(0/1\) 的前缀和，就很容易写出下面的伪代码：

// 初始化 f 数组
for(int i1 = 0; i1 <= 1; i1 ++) ··· for(int in = 0; in <= 1; in ++)if(in == 1) f[i1]···[in] += f[i1]···[in - 1];
···
for(int i1 = 0; i1 <= 1; i1 ++) ··· for(int in = 0; in <= 1; in ++)if(i1 == 1) f[i1]···[in] += f[i1 - 1]···[in];

因为每一维都是 \(0/1\)，我们显然可以把他们全部二进制压缩到一维。那么就可以这样写了：

for(int S = 0; S < (1 << n); S ++) f[S] = a[S];
for(int i = 0; i < n; i ++) for(int S = 0; S < (1 << n); S ++)if(S >> i & 1) f[S] += f[S ^ (1 << i)];

注意，只有第 \(i\) 维为 \(1\) 才需要转移。于是这道弱化版就做完了。

---

下面我们来看原题，原题要求对于每个 \(1 \le k < 2^n\)，\(\max\limits_{0 \le i < j < 2^n \land (i | j) \le k} a_i+a_j\)，其中 \(|\) 表示按位或。

这个没法直接求，因为有两个变量且两个变量相互作用，需要稍微转化一下，这个转化感觉比较神仙。

令 \(A_k = \max\limits_{i \ne j \land i|j=k} a_i+a_j\)，则 \(ans_k = \max\limits_{i=1}^k A_i\)，由于答案是求 \(\max\)，不妨扩展一下 \(A_i\) 的范围，把 \(i,j,k\) 看作二进制数，则让 \(A_k=\max\limits_{i \ne j \land i,j \subseteq k} a_i+a_j\)，这样处理对答案没有影响。

于是我们成功的把两个变量拆开了，这个式子可以拆开成下式：

\[A_k = \max_{i \subseteq k} a_i + \max_{i \ne j,j \subseteq k} a_j \]

相当于求出满足 \(i \subseteq k\) 的最大值和次大值，这样就可以用 SOS-dp 做了。

pii merge(pii x, pii y) {if(y.fi > x.fi) swap(x, y);return {x.fi, max(x.se, y.fi)};
}int main() {ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);cin >> n;for(int i = 0; i < (1 << n); i ++) cin >> a[i].fi, a[i].se = -INF;for(int i = 0; i < n; i ++) for(int S = 0; S < (1 << n); S ++)if(S >> i & 1) a[S] = merge(a[S], a[S ^ (1 << i)]);for(int S = 1; S < (1 << n); S ++) {res = max(res, a[S].fi + a[S].se);cout << res << "\n";}return 0;
}