【题目来源】
洛谷：P4310 绝世好题 - 洛谷
【题目描述】
给定一个长度为 \(n\) 的数列 \(a_i\)，求 \(a_i\) 的子序列 \(b_i\) 的最长长度 \(k\)，满足 \(b_i \& b_{i-1} \neq 0\) ，其中 \(2\le i\le k\)， \(\&\) 表示位运算取与。
【输入】
输入文件共 \(2\) 行。 第一行包括一个整数 \(n\)。 第二行包括 \(n\) 个整数，第 \(i\) 个整数表示 \(a_i\)。
【输出】
输出文件共一行。 包括一个整数，表示子序列 \(b_i\) 的最长长度。
【输入样例】
3
1 2 3
【输出样例】
2
【解题思路】
【算法标签】
《洛谷 P4310 绝世好题》 #枚举# #进制# #位运算#
【代码详解】
// 90分版本
#include <bits/stdc++.h>
using namespace std;int n; // 数组元素个数
int a[100005][2]; // a[i][0]存储元素值，a[i][1]存储以该元素结尾的最长子序列长度
int len; // 记录最长子序列长度int main()
{// 输入数组元素个数cin >> n;// 输入数组元素值for (int i = 1; i <= n; i++){cin >> a[i][0];}// 初始化第一个元素的最长子序列长度为1a[1][1] = 1;// 动态规划计算每个位置的最长子序列长度for (int i = 2; i <= n; i++){int maxn = 0; // 记录前i-1个元素中能与当前元素构成子序列的最大长度// 检查前i-1个元素for (int j = 1; j < i; j++){// 如果当前元素与前一个元素按位与结果不为0if (a[i][0] & a[j][0]){maxn = max(maxn, a[j][1]); // 更新最大长度}}// 当前元素的最长子序列长度 = 最大前驱长度 + 1a[i][1] = maxn + 1;// 更新全局最长子序列长度len = max(len, a[i][1]);}// 输出结果cout << len;return 0;
}
// 100分二维数组版本
#include <bits/stdc++.h>
using namespace std;int n; // 数组元素个数
int a[100005]; // 存储原始数组
int b[35]; // 存储2的幂次方值（1<<0到1<<30）
int dp[35][100005]; // dp[i][j]表示考虑前j个元素，最后一位包含第i位的最长子序列长度
int maxlen; // 记录最终的最长子序列长度int main()
{// 输入数组元素个数cin >> n;// 输入数组元素值for (int i = 1; i <= n; i++){cin >> a[i];}// 预处理2的幂次方值for (int i = 1; i <= 31; i++){b[i] = 1 << (i - 1); // 计算2^(i-1)}// 动态规划处理每个元素for (int i = 1; i <= n; i++){int maxn = 0; // 记录当前元素能扩展的最大子序列长度// 检查当前元素的每一位for (int j = 1; j <= 31; j++){// 如果当前元素包含第j位if (a[i] & b[j]){// 更新最大长度maxn = max(maxn, dp[j][i - 1]);}}maxn++; // 包含当前元素，长度+1// 更新dp数组for (int j = 1; j <= 31; j++){if (a[i] & b[j]){dp[j][i] = maxn; // 包含当前位则更新为新的最大长度}else{dp[j][i] = dp[j][i - 1]; // 不包含则保持前一个状态}}}// 在所有位中寻找最大长度for (int i = 1; i <= 31; i++){maxlen = max(maxlen, dp[i][n]);}// 输出结果cout << maxlen;return 0;
}
// 100分一维数组版本
#include <bits/stdc++.h>
using namespace std;int n; // 数组元素个数
int a[100005]; // 存储原始数组
int b[35]; // 存储2的幂次方值（1<<0到1<<30）
int dp[35]; // dp[i]表示当前以第i位结尾的最长子序列长度
int maxlen; // 记录最终的最长子序列长度int main()
{// 输入数组元素个数cin >> n;// 输入数组元素值for (int i = 1; i <= n; i++){cin >> a[i];}// 预处理2的幂次方值for (int i = 1; i <= 31; i++){b[i] = 1 << (i - 1); // 计算2^(i-1)}// 动态规划处理每个元素for (int i = 1; i <= n; i++){int maxn = 0; // 记录当前元素能扩展的最大子序列长度// 检查当前元素的每一位for (int j = 1; j <= 31; j++){// 如果当前元素包含第j位if (a[i] & b[j]){// 更新最大长度maxn = max(maxn, dp[j]);}}maxn++; // 包含当前元素，长度+1// 更新dp数组for (int j = 1; j <= 31; j++){if (a[i] & b[j]){dp[j] = maxn; // 更新以第j位结尾的最长子序列长度}}}// 在所有位中寻找最大长度for (int i = 1; i <= 31; i++){maxlen = max(maxlen, dp[i]);}// 输出结果cout << maxlen;return 0;
}
【运行结果】
3
1 2 3
2