【代码源每日一题】最长有趣子序列

我就是我 2024-03-26 20:00 87阅读 0赞

**....为什么审核一直不过**

题意：

![4de6189cd74886d6881b1a6cb06d0d89.png][]

思路：

感觉这道题我绝对写过啊，但是不知道为什么没找到题解

首先n^2的暴力DP肯定T，那么就要用到bitmask的一些trick了

**我们去考虑状态转移的特殊性质**

当两个数与起来不等于0的时候可以转移

因此可以设bit\[k\]表示前缀这些数里面第k位最长有趣子序列的长度，dp\[i\]为前i个数的最长有趣子序列长度

那么在考虑转移dp\[i\]的时候，去统计每个位为1的时候的长度最大值，然后转移

转移之后更新bit数组就行

**新的感悟：当暴力DP行不通而考虑更换DP定义的时候，可以去考虑转移的时候的特殊性质**

Code：

#include <bits/stdc++.h>
    using namespace std;
    #define int long long
    const int mxn=1e6+10;
    
    int n;
    int a[mxn],bit[33],dp[mxn];
    void solve(){
        cin>>n;
        for(int i=1;i<=n;i++) cin>>a[i];
        for(int i=1;i<=n;i++){
            int mx=-1;
            for(int j=30;j>=0;j--){
                if((a[i]>>j)&1) mx=max(mx,bit[j]);
            }
            dp[i]=mx+1;
            for(int j=30;j>=0;j--){
                if((a[i]>>j)&1) bit[j]=max(bit[j],dp[i]);
            }
        }
        cout<<dp[n]<<'\n';
    }
    signed main(){
        ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
        int __=1;//cin>>__;
        while(__--)solve();return 0;
    }

[4de6189cd74886d6881b1a6cb06d0d89.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/26/73f1eb389e414748ac00d284d2984c8e.png