Atcoder Regular100 C

未分类

---

给定长度为$2^n(1 \leq n \leq 18)$的数组$\{A_0,A_1,...,A_{2^n-1}\},1\leq a_i \leq 10^9$,定义:

$$B_k=max\{A_i+A_j|i<j, (i|j)\leq k\}$$
这里的$|$是按位或运算.
求$B_1,B_2,...,B_{2^n-1}.$

先声明一个结论：
令$bit(i)$表示$i$的二进制表示的$1$的个数.

$$\sum_{i=0}^{2^n-1}2^{bit(i)}=O(3^n)$$
那么可以这样计算$B_k$,令$s_k=\{A_i|(i|k)=k\}.$
$$\begin{align*} C_k&=max(s_k)+sec(s_k) \\ B_k&=max(B_{k-1},C_k) \end{align*}$$

正确性显然,时间复杂度是$O(3^n).$

示例代码:

for(int k=1;k<(1<<n);k++){
    int max=0,sec=0;
    for(int i=k;i>=0;i--){
        i&=k;
        if(A[i]>max){
            sec=max,max=A[i];
        }
        else if(A[i]>sec){
            sec=A[i];
        }
        B[k]=max(B[k-1],max+sec);
    }
}