51nod 3179 绝世好题

3179 绝世好题

他仅仅要求序列最长的长度，我们可以引用最长上升子序列的思想（有些隐蔽），设状态 \(dp[i]\) 为二进制第 i 位为 1 的最长序列长度，对于一个数 10101 \(dp[1],dp[3],dp[5]\) 都应该加一，对他们的数值取个最大值，并将他们的状态与最大值比较更新。

下列代码为上述思路：

#include<bits/stdc++.h>
using namespace std; 
#define ll long long 
int n;
ll a;

ll dp[35];
ll ans=0;
int main(){
	ios::sync_with_stdio(false);
    cin>>n;
    for(int i=1;i<=n;i++){
    	cin>>a;
    	ll mx=1;
    	for(int i=0;i<=30;i++){
	   		if(a&(1<<i)){
	   			mx=max(mx,dp[i]+1);
			}	
		} 
		for(int i=0;i<=30;i++){
			if(a&(1<<i)){
	   			dp[i]=max(dp[i],mx);
			}
			ans=max(ans,dp[i]);	
		}
	}
   
	cout<<ans;
    return 0;             
}