夏晓光(loveJY)的博客

这个DP妙啊

首先拿到题我们有dp[i][j]表示到i为止前一个数为j的最长and不为0序列是什么

然后转移时考虑枚举上一个哪个and起来不为0就好

但是这样你会发现没办法优化,问题是出在状态不够优秀上....

考虑二进制每一位都是独立的,那我们可不可以dp第二维记某一位为1的然后转移呢?

好像可以,但是转移的时候要小心了,对于数a,它能使所有二进制下a&为1的状态都加一,也能使所有二进制为1的状态之间互相转移!

举个例子,3可以使$dp[2]=max(dp[1],dp[2])+1....$

代码也就不难了

code

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int MAXN=1e5+7;

int n;
int a[MAXN],dp[MAXN],ans;

int main() {
	scanf("%d",&n);
	for(int i=1; i<=n; ++i)scanf("%d",&a[i]);
	for(int i=1; i<=n; ++i) {
		int qwq=0;
		for(int j=0; j<=30; ++j) {
			if(a[i]&(1<<j)) {
				qwq=max(dp[j],qwq);
			}
		}
		for(int j=0; j<=30; ++j) {
			if(a[i]&(1<<j)) {
				dp[j]=max(dp[j]+1,qwq+1);
			}
		}
	}
	for(int j=0; j<=30; ++j) {
		ans=max(ans,dp[j]);
	}
	printf("%d\n",ans);
	return 0;

}