绝世好题
题目描述
给定一个长度为 \(n\) 的数列 \(a_i\),求 \(a_i\) 的子序列 \(b_i\) 的最长长度 \(k\),满足 \(b_i \& b_{i-1} \ne 0\),其中 \(2\leq i\leq k\), \(\&\) 表示位运算取与。
输入格式
输入文件共 2 行。
第一行包括一个整数 \(n\)。
第二行包括 \(n\) 个整数,第 \(i\) 个整数表示 \(a_i\)。
输出格式
输出文件共一行。
包括一个整数,表示子序列 \(b_i\) 的最长长度。
样例 #1
样例输入 #1
3
1 2 3
样例输出 #1
2
提示
对于100%的数据,\(1\leq n\leq 100000\),\(a_i\leq 10^9\)
解析
两个数&不等于0,则这两个数的二进制中至少有一位都是1,我们设\(f_i\)表示序列末尾的数二进制下第i位为1的最大长度(可能有点不好理解),对于每个数x,枚举他的每个二进制位,如果为1,则可以转移。
本题的DP有点神奇且抽象,思维难度还是比较高的。
代码
#include <bits/stdc++.h>
using namespace std;
int f[35], ans;
int main() {
int n; cin >> n;
for (int i = 1; i <= n; i ++) {
int x; cin >> x;
int k = 0;
for (int j = 0; j <= 30; j ++)
if ((1 << j) & x) k = max(k, f[j] + 1);
for (int j = 0; j <= 30; j ++)
if ((1 << j) & x) f[j] = k;
ans = max(ans, k);
}
cout << ans << '\n';
}