BZOJ 절세호제(DP)

1809 단어 DP

4300: 절세의 좋은 문제


Time Limit: 1 Sec  
Memory Limit: 128 MB
Submit: 1948  
Solved: 1027
[ Submit][ Status][ Discuss]

Description


길이가 n인 수열ai를 정하고ai의 하위 서열bi의 가장 긴 길이를 구하여bi&bi-1을 만족시킵니다!=0(2<=i<=len).

Input


입력 파일은 모두 두 줄입니다.
첫 번째 줄은 정수 n을 포함한다.
두 번째 줄은 n개의 정수를 포함하고, 두 번째 정수는ai를 표시한다.

Output


출력 파일은 한 줄입니다.
하위 서열bi의 가장 긴 길이를 나타내는 정수를 포함합니다.

Sample Input


3 1 2 3

Sample Output


2

HINT


n<=100000,ai<=2*10^9
Source
먼저 두 개의 수가 0이면 이 두 개의 수의 이진법 표시 중 한 명당 반드시 0이 있다는 것을 쉽게 생각할 수 있다
만약 이 두 사람이 모두 1이었다면 0이 되지 않았을 텐데......
DP[i]로 하여금 1위가 1인 경우 하위 시퀀스의 최대 길이를 나타냅니다.
 
#include
#include
#include
#include
#include
#include
#include
using namespace std;
typedef long long  ll;
#define maxn 550000
int dp[55],a[maxn];
int  main(void)
{
	int n,i,j,tmp,ans;
	scanf("%d",&n);
	for(i=1;i<=n;i++)
		scanf("%d",&a[i]);
	for(i=1;i<=n;i++)
	{
		tmp=0;
		for(j=0;j<31;j++)
			if(a[i]&(1<

좋은 웹페이지 즐겨찾기