Luogu P4310 绝世好题

题目大意

% 　　给定 $n$ 个数组成的序列 $A=\{a_i\}$，定义一个长度为 $N$ 的序列 $B=\{b_i\}$ 合法当且仅当 $\forall i\in [1,N]\cap \mathbb{Z},b_i\text{and}{b}_{i-1}\ne 0$，求 $A$ 中最长的合法子序列长度。 % 　　数据范围　$1⩽n⩽10^5,1⩽a_i⩽10^9$

题解

% 　　考虑动态规划，定义 $f[i]$ 表示以第 $i$ 个数为结尾的合法子序列长度，转移如下$$f[i]=\underset{j\in [1,i),a_i\text{and}{a}_j\ne 0}{\max }f[j]+1$$

% 　　这样做的时间复杂度为 $\Theta (n^2)$，空间复杂度为 $\Theta (n)$。

#include<cstdio> #define max(a,b) (a>b?a:b) #define maxn 100010 int a[maxn],f[maxn],n; int main(){ scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%d",&a[i]); register int ans=0; for(register int i=1;i<=n;i++){ f[i]=1; for(register int j=1;j<i;j++) if(a[j]&a[i]) f[i]=max(f[j]+1,f[i]); ans=max(ans,f[i]); } printf("%d\n",ans); return 0; }

% 　　考虑更换定义 $f[i][k]$ 表示前 $i$ 个数能选出的子序列中，子序列最后一个数的二进制下第 $j$ 位(从低位(第0位开始)，向高位编号)为 $1$ 的最长长度。状态转移如下： $$f[i][j]=\max \{\begin{array}{ll}f[i-1][j]& \\ & \\ \begin{array}{r}\underset{a_i\text{and}{2}^k=1}{\max }f[i-1][k]+1\end{array}& ,a_i\text{and}{2}^j=1\end{array}$$

% 　　这样朴素转移时间复杂度为 $\Theta (n{\log }_2^2{a}_i)$，空间复杂度可以降到 $\Theta ({\log }_2^2{a}_i)$（降维）

#include<bits/stdc++.h> using namespace std; #define maxn 1000010 int n,f[maxn][32]; int main(){ int ans=0; scanf("%d",&n); for(int i=1,a;i<=n;i++){ scanf("%d",&a); for(int j=0;j<=30;j++){ f[i][j]=f[i-1][j]; if(!(a&(1<<j))) continue; for(int k=0;k<=30;k++){ if(a&(1<<k)) f[i][j]=max(f[i][j],f[i-1][k]+1); } ans=max(ans,f[i][j]); } } printf("%d\n",ans); return 0; }

% 　　考虑到转移的时间瓶颈在于需要枚举上一个数和这一个数在那一位上相同，而这个过程与 $j$ 无关，因此我们可以处理出这部分的答案，再进行转移。时间复杂度 $\Theta (n{\log }_2{a}_i)$。

#include<bits/stdc++.h> using namespace std; #define maxn 1000010 int n,f[maxn][32]; int main(){ int ans=0; scanf("%d",&n); for(int i=1,a;i<=n;i++){ scanf("%d",&a); int tran=0; for(int k=0;k<=30;k++) if(a&(1<<k)) tran=max(tran,f[i-1][k]+1); for(int j=0;j<=30;j++){ if(a&(1<<j)) f[i][j]=max(f[i][j],tran); else f[i][j]=f[i-1][j]; ans=max(ans,f[i][j]); } } printf("%d\n",ans); return 0; }