【BZOJ4300】—絕世好題（二進制dp）

傳送門

考慮到只需要bi&bi?1=?0b_i\&b_{i-1} =\not0bi?&bi?1?=??0

由于$\&$，我們考慮二進制下只需要一位不為0就可以了
$f[i]$表示當前數下，第$i$位不為0的最優長度

那就是需要枚舉當前這個數所有位就可以轉移了

#include<bits/stdc++.h>
using namespace std;
inline int read(){char ch=getchar();int res=0,f=1;while(!isdigit(ch)){if(ch=='-')f=-f;ch=getchar();}while(isdigit(ch))res=(res<<3)+(res<<1)+(ch^48),ch=getchar();return res*f;	
} 
int f[35],n;
int main(){n=read();for(int i=1;i<=n;i++){int a=read(),t=1;for(int j=0;j<=30;j++)if(a&(1<<j))t=max(f[j]+1,t);for(int j=0;j<=30;j++)if(a&(1<<j))f[j]=t;}n=0;for(int i=0;i<=30;i++)n=max(n,f[i]);cout<<n;
}