P4310 绝世好题

题目

P4310 绝世好题

算法标签: 动态规划, 线性$dp$, 位运算

思路

数据范围$n=10^5$, 假设定义状态表示$f[i]$表示以$i$为结尾的最长的符合条件的子序列的长度, 那么需要枚举上一个位置$j$, 观察$w[i]$ & $w[j]$的结果是否是$0$如果是$0$不能从该状态转移过来, 那么能够转移的状态就是$1\sim i-1$当中符合条件的$j$的$f[j]$的最大值, 如果直接枚举时间复杂度是$O(n^2)$会超时, 需要进行优化

发现直接优化状态计算没办法优化, 考虑重新对集合进行划分, 定义状态表示$f[i]$表示以第$i$位为$1$的所有子序列中长度最长的子序列, 考虑如何进行状态转移

每加入一个数字, 枚举所有位置$0\sim 31$, 检查每一位是否是$1$, 如果是$1$更新最大值, 然后得到最大后再更新回状态转移数组, 算法时间复杂度$O(n\log m)$可以通过

代码

#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

const int N = 1e5 + 10, M = 32;

int n, f[M];

int main() {
   
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    cin >> n;
    int ans = 1;
    for (int i = 1; i <= n; ++i) {
   
        int val;
        cin >> val;
        int tmp = 1;
        for (int k = 0; k < M; ++k) {
   
            if (val >> k & 1) tmp = max(tmp, f[k] + 1);
        }
        for (int k = 0; k < M; ++k) {
   
            if (val >> k & 1) f[k] = max(f[k], tmp);
        }
        ans = max(ans, tmp);
    }

    cout << ans << "\n";
    return 0;
}