P4310题解

0 前言

好久没做题了好像

但是不重要

1 题意

原题面写的十分清楚，可以 [去看](P4310 绝世好题 - 洛谷)。

2 思路

拿到这个题，首先想到DP。而且发现没有序列上的区间最优问题，考虑使用线性DP。

我们用 $f_i$ 来表示前 $i$ 个元素中所能选出的 $k$ 的最大值。容易发现如下转移：

$$f_i=max\{f_i,f_{lst_i}+1\}$$

因此接下来我们考虑如何处理 $lst_i$。

我们阅读题目发现，题目要求新的子序列的相邻两项的按位与结果不为 $0$，同时我们发现两个数按位与结果不为 $0$ 的充要条件是 这两个数在二进制表示下至少存在一位都为 $1$。

因此我们可以考虑对于当前元素二进制下的每一位进行考虑。通过上述结论，我们发现，只要上一个元素和这个元素在二进制下有一位都为 $1$，那么我们就可以从上一个元素转移过来。

因此，我们用 $lst_{i,j}$ 表示 $i$ 位置元素的上一个二进制下 $j$ 位为 $1$ 的元素编号。因此，我们就可以很容易写出最后的状态转移方程：

$$f_i=max\{f_{lst_{i,j}}\}+1$$

3 具体实现

部分示例代码如下：

signed main(){
    n=read();
    for(int i=1;i<=n;++i)a[i]=read();
    for(int i=0;i<=30;++i)lst[1][i]=0;
    for(int i=2;i<=n;++i){
        for(int j=0;j<=30;++j){
            if((a[i-1]>>j)&1)lst[i][j+1]=i-1;
            else lst[i][j+1]=lst[i-1][j+1];
        }
    }
    f[1]=1;
    for(int i=2;i<=n;++i){
        for(int j=0;j<=30;++j){
            if((a[i]>>j)&1)f[i]=max(f[i],f[lst[i][j+1]]+1);
        }
    }
    int ans=0;
    for(int i=1;i<=n;++i)ans=max(ans,f[i]);
    printf("%lld",ans);
    return 0;
}

关于时间复杂度：

预处理和DP的两层循环都分别是 $n$ 次和 $30$ 次，因此最终复杂度在极限数据下接近 $O(n\log n)$ 这个数量级。

4 后记

待补。