题意：给你一个序列a，求最长子序列b满足$b_i&b_{i-1} e 0$
思路：类似于最长不下降子序列，以f[i]代表以i为结尾的最长b的长度，$O(n^2)$ 80分（数据水）
正解：以f[i]代表目前为止b序列尾元素二进制第i位为1的长度
那么就简单了
当前状态可以由它二进制所有为1的i转移过来
而且还可以转移到所有二进制为1的i
#include<cstdio> #include<iostream> #include<cstring> #include<cctype> #include<algorithm> using namespace std; #define olinr return #define _ 0 #define love_nmr 0 #define DB double inline int read() { int x=0,f=1; char ch=getchar(); while(!isdigit(ch)) { if(ch=='-') f=-f; ch=getchar(); } while(isdigit(ch)) { x=(x<<1)+(x<<3)+(ch^48); ch=getchar(); } return x*f; } inline void put(int x) { if(x<0) { x=-x; putchar('-'); } if(x>9) put(x/10); putchar(x%10+'0'); } int n; int a[105050]; int f[50]; int ans; int main() { n=read(); for(int i=1;i<=n;i++) a[i]=read(); for(int i=1;i<=n;i++) { int now=1; for(int j=0;j<=30;j++) if((1<<j)&a[i]) now=max(now,f[j]+1); //转移 for(int j=0;j<=30;j++) if((1<<j)&a[i]) f[j]=max(f[j],now); //更新 ans=max(ans,now); } put(ans); olinr ~~(0^_^0)+love_nmr; }