Description

題庫鏈接

給定一個長度為 \(n\) 的數列 \(a_i\) ，求 \(a_i\) 的子序列 \(b_i\) 的最長長度，滿足 \(b_i\wedge b_{i-1}\neq 0\) （ \(\wedge\) 表示按位與）

\(1\leq n\leq 100000\)

Solution

令 \(f_i\) 為二進制第 \(i\) 位為 \(1\) 最長子序列長度。轉移只要枚舉當前數二進制位下為 \(1\) 的位就好了。

Code

#include <bits/stdc++.h> using namespace std; const int N = 100000+5;int n, a, f[N], bin[35], ans;void work() {scanf("%d", &n); bin[0] = 1; for (int i = 1; i <= 30; i++) bin[i] = (bin[i-1]<<1);for (int i = 1; i <= n; i++) {scanf("%d", &a); int ans = 0;for (int i = 0; i <= 30; i++) if (a&bin[i]) ans = max(ans, f[i]);for (int i = 0; i <= 30; i++) if (a&bin[i]) f[i] = ans+1;}for (int i = 0; i <= 30; i++) ans = max(ans, f[i]);printf("%d\n", ans); } int main() {work(); return 0; }

轉載于:https://www.cnblogs.com/NaVi-Awson/p/9235777.html

總結

以上是生活随笔為你收集整理的[BZOJ 4300]绝世好题的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。