【代码源每日一题】最长有趣子序列-蒲公英云

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

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

….为什么审核一直不过

题意：

思路：

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

首先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;
}