P4310 绝世好题

#include 
using namespace std;
using PII = pair<int,int>;
using ll  = long long;
using VI = vector<int>;
using namespace std;
int res = 0;
int n;
int a[1000010];
int dp[33];
int main(){
    cin>>n;
    for(int i = 1; i <= n; i++) cin>>a[i];
 
    //每一位都没有重叠的时候 & 完是 0
    //只要有一位能保持1 & 1 就不是0
    // 01  10  11
    //第 i 个 数  第 j为非 0 的最大长度
    //是两两之间，不是整个序列 & 起来
    //第 i 个数 结尾 ，
    for(int i = 1; i <= n; i++){
 
        int v = 1;
        //先看看这个数到的能转移的最大长度是多少
        for(int j = 0; j <= 31 ;j++){
            if(a[i] >> j & 1){
                v = max(dp[j] + 1 , v);
            }
        }
        //更新以j结尾 的所有长度
        for(int j = 0; j <= 31 ;j++){
            if(a[i] >> j & 1){
                dp[j] = max(dp[j] , v);
            }
        }
        res = max(res,v);
 
 
    }
    cout<
 
 
    //1 0 1 1          13
    //0 0 0 0 1        16
    //1 0 0 1           9
    //0 0 1 1           12
    //0 0 1 0           4
    //0 0 1 0           4
    //0 1 0 0 1         18
 
 
 
 
 
}

因为是相邻两个数之间的 & 不等于1

所以对于每个数，我们只关心他的上一个数 哪一位为 1 

或者这么说，一个数字011接到001和010 后的长度分别为4 ， 5

那么我们只需要当前的dp情况 dp[001] = 5 dp[010] = 5