傳送門

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

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

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

#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; }

轉載于:https://www.cnblogs.com/stargazer-cyk/p/11145675.html

總結

以上是生活随笔為你收集整理的【BZOJ4300】—绝世好题（二进制dp）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。