[BZOJ 4300]绝世好题

Description

题库链接

给定一个长度为 (n) 的数列 (a_i) ，求 (a_i) 的子序列 (b_i) 的最长长度，满足 (b_iwedge b_{i-1} eq 0) （ (wedge) 表示按位与）

(1leq nleq 100000)

Solution

令 (f_i) 为二进制第 (i) 位为 (1) 最长子序列长度。转移只要枚举当前数二进制位下为 (1) 的位就好了。

Code

#include <bits/stdc++.h>
using namespace std;
const int N = 100000+5;

int n, a, f[N], bin[35], ans;

void work() {
    scanf("%d", &n); bin[0] = 1; for (int i = 1; i <= 30; i++) bin[i] = (bin[i-1]<<1);
    for (int i = 1; i <= n; i++) {
        scanf("%d", &a); int ans = 0;
        for (int i = 0; i <= 30; i++) if (a&bin[i]) ans = max(ans, f[i]);
        for (int i = 0; i <= 30; i++) if (a&bin[i]) f[i] = ans+1;
    }
    for (int i = 0; i <= 30; i++) ans = max(ans, f[i]);
    printf("%d
", ans);
}
int main() {work(); return 0; }