自动搬运

查看原文

来自洛谷，原作者为

	winxp_qwq 退役菜鸡

搬运于2025-08-24 21:58:50，当前版本为作者最后更新于2018-03-12 17:24:27，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

其实就直接dp就好了

令dp[i]表示数列到目前为止最后一项第i位为1的最大子序列长度，每读入一个数时就大力转移。一个数可以被它所有的二进制位的dp值转移，然后把它转移到它的所有二进制位的dp值上。

复杂度nlogn

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