洛谷 P4310 绝世好题

url: https://www.luogu.com.cn/problem/P4310

tag:
动态规划，位运算

思路：
如果用求最长上升子序列的方式来求会超时。这时我们可以观察到因为要满足b_i & b_{i - 1} != 0，所以对于以a_i 结尾的数来说，只要是某一个序列末尾的数的某一位和a_i 都是1就可以想接。所以可以用一个数列bit来存某一位为1时的最长序列。之后更新时只需要枚举a_i 的每一位为1的情况，更新f就行。最后求出最大值后，用这个最大值再来更新当前情况下的bit数组值。对于枚举每一位可以通过lowbit函数求出最低位的1（2^k 的形式），之后再通过map log_2来映射每一个2^k 的 k值即为位数。

代码：

#include <iostream>
#include <map>
#include <cstring>
#include <cstdio>
#include <algorithm>
using namespace std;
const int N = 1e6 + 10;
int a[N];
int n;
int ans;
int f[N];
int bit[N];
map<int, int> log_2;
int lowbit(int x)
{
    return x & -x;
}
int main()
{
    cin >> n;
    for (int i = 0, j = 1; i <= 31; i ++, j <<= 1)
    {
        log_2[j] = i;
    }
    for (int i = 1; i <= n; i ++) cin >> a[i];
    for (int i = 1; i <= n; i ++)
    {
        for (int j = a[i], low = lowbit(j); j; j -= low, low = lowbit(j))
        {
            f[i] = max(f[i], bit[log_2[low]] + 1);
        }
        for (int j = a[i], low = lowbit(j); j; j -= low, low = lowbit(j))
        {
            bit[log_2[low]] = max(bit[log_2[low]], f[i]);
        }
        ans = max(ans, f[i]);
    }
    cout << ans << endl;
    return 0;
}