题目概述
ps：题目名真自恋。 给定一个序列a，求一个最长的子序列b，子序列相邻两个元素b[i-1]和b[i]满足(b[i-1]&b[i])!=0。
解题报告
刚开始一看到就想到朴素DP，f[i]表示i必选的最优解，但是
O(n2)
扛不住。我们分析一下f[j]能推到f[i]的要求：(a[j]&a[i])!=0，这个要求进一步理解就是a[j]和a[i]二进制至少有一位均为1。所以我们可以从二进制下手！f[i]表示二进制第i位为1的最优解，则对于a[i]来说，如果a[i]第j位为1，那么当前状态就可以从f[j]推过来，刷出max(f[j])，再把a[i]所有为1的位置都修正就行了。效率
O(30∗n)
。
示例程序
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=
100000,maxt=
30;
int n,a[maxn+
5],f[maxt+
5];
int main()
{
freopen(
"program.in",
"r",stdin);
freopen(
"program.out",
"w",stdout);
scanf(
"%d",&n);
for (
int i=
1;i<=n;i++)
scanf(
"%d",&a[i]);
for (
int i=
1;i<=n;i++)
{
int MAX=
0;
for (
int j=
0;j<=
30;j++)
if (a[i]&(
1<<j)) MAX=max(MAX,f[j]);
for (
int j=
0;j<=
30;j++)
if (a[i]&(
1<<j)) f[j]=max(f[j],MAX+
1);
}
int MAX=
0;
for (
int j=
0;j<=
30;j++) MAX=max(MAX,f[j]);
printf(
"%d\n",MAX);
return 0;
}
