题解 P4310 【绝世好题】
winxp_qwq
2018-03-12 17:24:27
其实就直接dp就好了
令dp[i]表示数列到目前为止最后一项第i位为1的最大子序列长度，每读入一个数时就~~大力~~转移。一个数可以被它所有的二进制位的dp值转移，然后把它转移到它的所有二进制位的dp值上。
复杂度nlogn
```cpp
#include <bits/stdc++.h>
using namespace std;
int dp[32];
int main(){
int n;
scanf("%d",&n);
int a,b,c,i,j,k,ans=0;
for(a=1;a<=n;a++)
{
scanf("%d",&b);
k=1;
for(c=0;c<=30;c++)
if((1<<c)&b) k=max(dp[c]+1,k);
for(c=0;c<=30;c++)
if((1<<c)&b) dp[c]=max(dp[c],k);
ans=max(ans,k);
}
printf("%d\n",ans);
return 0;
}
```