【链接】 bzoj4300
【题目大意】 给你一个数列a，求a的子序列b，是bi&bi-1!=0。
【解题报告】 首先我们有个笨蛋的想法，就是n^2枚举当前状态和上一状态刷DP。但是时间复杂度似乎扛不住。所以就要换一个思路，bi&bi-1!=0，不就是两个数在二进制下相对应的位置至少有一个位置都是1。所以定义f[i]表示二进制下所对应的第i位是1的最长子序列。如果当前推到第i个数，则从所对应的二进制是1的位置刷目前所得到的最大值，然后将这个最大值赋给二进制下是1的位置。答案就是max(f[0~30])(最多也就31位)，复杂度就降到了O(30*n)。
#include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int maxn=33; int n,ans,f[maxn]; inline int Read() { int res=0; char ch=getchar(); while (ch<'0'||ch>'9') ch=getchar(); while (ch>='0'&&ch<='9') res=res*10+ch-48,ch=getchar(); return res; } int main() { freopen("4300.in","r",stdin); freopen("4300.out","w",stdout); memset(f,0,sizeof(f)); n=Read(); ans=0; for (int i=1; i<=n; i++) { int x=Read(),Max=0; for (int j=x,k=0; j; j>>=1,k++) if (j%2) Max=max(Max,f[k]); for (int j=x,k=0; j; j>>=1,k++) if (j%2) f[k]=Max+1; } for (int i=0; i<=30; i++) ans=max(ans,f[i]); printf("%d",ans); return 0; }