「BZOJ 4300」绝世好题

Description

题目链接:BZOJ 4300

给定一个长度为 $n$ 的数列 $a_i$,求 $a_i$ 的子序列 $b_i$ 的最长长度 $len$,满足 $b_i\ \text{AND}\ b_{i-1}\neq 0$($2\le i\le len$)。

数据范围:$n\le 10^5$,$a_i\le 2\times 10^9$


Solution

我们可以设计出一个不朴素的 $\text{DP}$ 状态 $f[i]$ 表示考虑前 $i$ 个数的最长长度,转移为 $f[i]=\max\{f[j]+1\}$($a_i\ \text{AND}\ a_j\neq 0$)。

考虑优化,发现这个东西和 $\text{LIS}$ 非常类似。由于 $a\ \text{AND}\ b\neq 0$ 意味着一定有一位为 $1$,所以我们用 $f[i]$ 表示第 $i$ 位为 $1$ 的最长长度。每次读入一个 $x$,我们记 $s=\max\{f[i]\}+1$($x$ 的第 $i$ 位为 $1$),然后用 $s$ 去更新 $f[i]$,最后的答案即为 $\max\{f[i]\}$。

时间复杂度:$O(n\log a_i)$


Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <cstdio>
#include <algorithm>

const int N=35;
int n,f[N];

int main() {
scanf("%d",&n);
for(int x;n--;) {
scanf("%d",&x);
int mx=1;
for(int i=0;i<=30;++i) if(x&(1<<i)) mx=std::max(mx,f[i]+1);
for(int i=0;i<=30;++i) if(x&(1<<i)) f[i]=std::max(f[i],mx);
}
int ans=0;
for(int i=0;i<=30;++i) ans=std::max(ans,f[i]);
printf("%d\n",ans);
return 0;
}
0%