problem

cf鏈接

solution

讀完題先直接暴力 $dp$ 拿出來，$d{p}_i={\max }_{j<i}\{d{p}_j+(f_i\&f_j)\}$。

誰能優化誰就是爸爸

假設存在 $j<k<i$，且 $f_i\&f_j$ 為 $1$ 的最高二進制位是 $p$，且 $f_i\&f_k,f_k\&f_j$ 的第 $p$ 位也為 $1$。

那么選擇 $j,k,i$ 肯定比 $j,i$ 跳過 $k$ 要優。

因為 $f_j\&f_i$ 比 $p$ 更高的位全是 $0$，而加上 $k$，$2^p$ 就會計入兩次貢獻，說不定更高位還要額外0貢獻產生，但都一定比只算一次 $2^p$ 大。

所以我們只需要對于每一個二進制位，記錄最近的該位為 $1$ 的數下標即可。

到時候直接用 $f_i$ 二進制也為 $1$ 的那些位置進行轉移，轉移完后再更新。

$d{p}_i={\max }_{f_i>>j\&1}\{d{p}_{g_j}+(f_i\&f_{g_j})\}$。

時間復雜度從 $O(n^2)$ 銳減成 $O(n\log v)$。

位運算常考察兩個點：拆成二進制位獨立計算以及高二進制位決定/優先低二進制位。

code

#include <bits/stdc++.h> using namespace std; #define int long long #define maxn 1000005 int n; int f[maxn], dp[maxn], g[60];signed main() {scanf( "%lld", &n );for( int i = 1;i <= n;i ++ ) scanf( "%lld", &f[i] );for( int i = 1;i <= n;i ++ ) {for( int j = 40;~ j;j -- )dp[i] = max( dp[i], dp[g[j]] + (f[g[j]] & f[i]) );for( int j = 40;~ j;j -- )if( f[i] >> j & 1 ) g[j] = i;}int ans = 0;for( int i = 1;i <= n;i ++ ) ans = max( ans, dp[i] );printf( "%lld\n", ans );return 0; } /* dp[i]=max{ dp[j]+a[i]&a[j] } consider k(j<k<i) satisfy the highest digit p a[i]&a[j] a[i]&a[k] a[j]&a[k] all 1 it's better to choose j k i instead of j i calc 2^p twice is bigger than once,of course we just need to choose the nearest node for each digit O(n^2)->O(n \log v) */

總結

以上是生活随笔為你收集整理的[CodeForces gym 102956 D] Bank Security Unification（位运算优化dp）的全部內容，希望文章能夠幫你解決所遇到的問題。

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