回顾：最长子序列问题
先让我们回想一下最长上升子序列是如何解决的。
定义 $dp[i]$ 表示以 $a[i]$ 结尾的最长子序列的长度。
那么 $dp[i]$ 就是在 $[1,i-1]$ 中找到一个满足 $a[j]<a[i]$ 且 $dp[j]$ 最大的 $j$，则 $dp[i]=dp[j]+1$。
这是 $\mathcal O(n^2)$ 的做法。
对于 $\mathcal O(n\log n)$ 做法，则是令 $dp[i]$ 表示长度为 $i$ 的子序列的最后一位，然后每次加入的时候就在 $dp$ 上二分加入，最后查询 $i$ 的最大值即可。
最长上升子序列的推广
现在来思考本题。
$\mathcal O(n^2)$ 做法
仍然定义 $dp[i]$ 表示以 $a[i]$ 结尾的满足条件的最长子序列的长度。
一个 $\mathcal O(n^2)$ 的做法是，$i$ 枚举 $[1,n]$，$j$ 枚举 $[1,i-1]$，若 $a[i]\ \&\ a[j]>0$，则有：
\[dp[i]\leftarrow \max(dp[i],dp[j])\]此时再有 $dp[i]\leftarrow dp[i]+1$，最终答案即 $\max\limits_{i=1}^ndp[i]$。
参考代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
//#include<bits/stdc++.h>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<iomanip>
#include<cstdio>
#include<string>
#include<vector>
#include<cmath>
#include<ctime>
#include<deque>
#include<queue>
#include<stack>
#include<list>
using namespace std;
const int N=100000;
int n,a[N+1],dp[N+1];
int main(){
/*freopen("test.in","r",stdin);
freopen("test.out","w",stdout);*/
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%d",a+i);
}
int Max=0;
for(int i=1;i<=n;i++){
for(int j=1;j<i;j++){
if(a[i]&a[j]){
dp[i]=max(dp[i],dp[j]);
}
}dp[i]++;
Max=max(Max,dp[i]);
}printf("%d\n",Max);
/*fclose(stdin);
fclose(stdout);*/
return 0;
}
期望得分：$30\text{pts}$。
实际得分：$90\text{pts}$。
数据严重过水。
$\mathcal O(n\log n)$ 做法
我们可以尝试优化我们的做法。
回顾最长上升子序列问题，发现之所以能够优化，是因为二分的存在。
然而本题显然无法二分，考虑其他做法。
分析题目条件，序列元素之间只要有一个二进制位都是 $1$，就可以分到一组。
令 $dp[i]$ 表示末尾元素二进制位上权值为 $2^i$ 的位为 $1$ 的子序列的最长长度。
那么就看所有被 $a[i]$ 包含的 $2^j$ 的 $dp[j]$，取最大值后加 $1$ 可以得到以 $a[i]$ 结尾的最长子序列长度 $s$。此时我们又可以使用 $s$ 将这些 $dp[j]$ 全部更新。
最终答案即 $\max\limits_{i=1}^{\log V}dp[i]$。
AC 代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
//#include<bits/stdc++.h>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<iomanip>
#include<cstdio>
#include<string>
#include<vector>
#include<cmath>
#include<ctime>
#include<deque>
#include<queue>
#include<stack>
#include<list>
using namespace std;
int n,x,dp[30];
int main(){
// freopen("test.in","r",stdin);
// freopen("test.out","w",stdout);
scanf("%d",&n);
int ans=0;
for(int i=1;i<=n;i++){
scanf("%d",&x);
int Max=0;
for(int j=0;j<30;j++){
if(x&(1<<j))Max=max(dp[j],Max);
}Max++;
for(int j=0;j<30;j++){
if(x&(1<<j))dp[j]=max(dp[j],Max);
ans=max(ans,dp[j]);
}
}printf("%d\n",ans);
/*fclose(stdin);
fclose(stdout);*/
return 0;
}
