洛谷题单指南-动态规划2-P4310 绝世好题

原题链接：https://www.luogu.com.cn/problem/P4310

题意解读：求最长的子序列长度，使得每相邻两个元素 & 操作不为0。

解题思路：

直观来看，可以通过类似最长上升子序列的算法，进行状态转移，但是复杂度为O(n^2)，会超时

状态表示：dp[i]表示前i个数能产生满足条件的子序列的最长长度

状态转移：dp[i] = max(dp[1] + 1, dp[2] + 1, ... , dp[i-1] + 1)

初始值：dp[i] = 1

结果：max(dp[i])

90分代码：

#include <bits/stdc++.h>
using namespace std;

const int N = 100005;
int n;
int a[N];
int dp[N]; //dp[i]表示前i个数能产生满足条件的子序列的最长长度
int ans;

int main()
{
    cin >> n;
    for(int i = 1; i <= n; i++) cin >> a[i];

    for(int i = 1; i <= n; i++)
    {
        dp[i] = 1;
        for(int j = 1; j < i; j++)
        {
            if(a[i] & a[j]) //注意：如果要写成不等于0判断，(a[i]&a[j]) != 0要加括号才能作为整体计算，因为&优先级较低
            {
                dp[i] = max(dp[i], dp[j] + 1);
            } 
        }
        ans = max(ans, dp[i]);
    }
    cout << ans;

    return 0;
}

如何优化呢？

题目要求，子序列中相邻两数相&不为0，即在整数的二进制表示中，只要有相同位置的二进制位为1，就可以满足要求。

也就是说，对于每个数，只要其二进制位上是1，则该数可以对以该位置为1的数结尾的子序列的长度产生1个贡献。

那么，可以针对每个数a[i]，依次枚举每个二进制位，如果为1，则以该位置二进制为1的数结尾能产生的子序列长度就要加1，

对于同一个数a[i]，在其以每个为1的二进制位置结尾所能产生的子序列最大长度应该更新为各个位置子序列长度的最大值。

设f[i]表示以第i位为1的数结尾能产生的最长子序列长度，

对于每一个数a[i]，通过 a[i] & (1 << j)，j =0~31，来判断每一位是否为1，如果第j位为1，则记录f[j] + 1的最大值maxx，这个maxx就是以a[i]结尾能产生的最长子序列长度。

再对于a[i]，更新其每个为1的位上的f值，f[j] = maxx

重点说明：为什么要把a[i]二进制中每个为1位置的f值更新为maxx？

因为，能接在a[i]后面的数，只要满足与a[i]在任意相同二进制位为1即可，而a[i]能产生最大子序列长度是maxx，所有，a[i]的所有二进制为1的位置的f值都要更新为maxx。

记录最大的maxx即为答案。

100分代码：

#include <bits/stdc++.h>
using namespace std;

const int N = 100005;
int n;
int a[N];
int f[32]; //f[i]表示以第i位为1的数结尾产生的最长子序列长度,int一共32为，记录从0~31
int ans;

int main()
{
    cin >> n;
    for(int i = 1; i <= n; i++) cin >> a[i];

    int maxx = 0;
    for(int i = 1;i <= n; i++)
    {
        for(int j = 0; j <= 31; j++)
        {
            if(a[i] & (1 << j)) //如果a[i]第j位是1
            {
                maxx = max(maxx, f[j] + 1); //第j位为1结尾的子序列长度都要加1，记录最大值，即以a[i]结尾
            }
        }
        for(int j = 0; j <= 31; j++)
        {
            if(a[i] & (1 << j))
            {
                f[j] = maxx; //把a[i]各个位置为1对应的f值更新为maxx，因为能接在a[i]后面的数只要在a[i]任意为1的位置一致即可
            }
        }
        ans = max(ans, maxx);
    }
    cout << ans;

    return 0;
}