절세 호제 동태 기획

967 단어 동적 기획
주의ai가 반드시 <=10^9는 아니지만 <=2^31-1이어야 합니다.(출제자를 욕하고 싶어요...)
우리는 f[k]로 마지막 바이너리 k위가 1일 때의 최대치를 나타낼 수 있다. 그러면 x로 끝나는 수열의 최대치는max{f[k]+1}이고 x의 k위는 1이다.그리고 x로 답안을 업데이트하면 됩니다.
AC 코드는 다음과 같습니다.
#include<cstdio>
#include<iostream>
using namespace std;

int n,f[35],bin[35];
int read(){
	int x=0; char ch=getchar();
	while (ch<'0' || ch>'9') ch=getchar();
	while (ch>='0' && ch<='9'){ x=x*10+ch-'0'; ch=getchar(); }
	return x;
}
int main(){
	n=read(); int i,k,ans=0;
	bin[0]=1; for (i=1; i<=30; i++) bin[i]=bin[i-1]<<1;
	for (i=1; i<=n; i++){
		int x=read(),tmp=0;
		for (k=0; k<=30 && bin[k]<=x; k++) if (x&bin[k]) tmp=max(tmp,f[k]);
		tmp++; ans=max(ans,tmp);
		for (k=0; k<=30 && bin[k]<=x; k++) if (x&bin[k]) f[k]=max(f[k],tmp);
	}
	printf("%d
",ans); return 0; }

by lych
2016.3.8

좋은 웹페이지 즐겨찾기