题解：P12316 [蓝桥杯 2024 国 C] 循环位运算

· · 题解

洛谷 P12316

题意

给定 n 个数 A_i，每个数我们都将其视为一个 32 位的二进制数。你可以进行 m 次操作，每次选择任意一个数将其循环左移一次。

问做了不超过 m 次操作后，n 个数的和最大是多少。

思路

因为涉及位运算，所以不方便贪心，考虑 dp。

可以先预处理出每个 a_i 循环左移 j 次的结果。接着做背包 dp，设计状态 dp_{i,j} 表示当前考虑到第 i 个点，用了 j 次操作的最大和。

因此，只需枚举当前的点 i，到本次所用操作次数之和 j，以及本次操作次数 k，进行转移即可。转移式如下：

dp_{i,j}=\max\limits_{k}^{\min(31,j)}(dp_{i-1,j-k}+w_{i,k})

代码

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

const int N = 1010;

ll n, m, a[N], dp[N][N];
ll w[N][40];

int main(){
  cin >> n >> m;
  for(int i = 1; i <= n; i++){
    cin >> a[i];
  }
  for(int i = 1; i <= n; i++){
    for(int j = 0; j <= 32; j++){
      w[i][j] = ((a[i] << j) | (a[i] >> (32 - j))) % (1ll << 32);
    }
  }
  for(int i = 0; i <= n; i++){
    for(int j = 0; j <= m; j++){
      dp[i][j] = -1e16;
    }
  }
  dp[0][0] = 0;
  for(int i = 1; i <= n; i++){
    for(int j = 0; j <= m; j++){
      for(int k = 0; k <= min(31, j); k++){
        dp[i][j] = max(dp[i][j], dp[i - 1][j - k] + w[i][k]);
      }
    }
  }
  ll ans = -1e16;
  for(int i = 0; i <= m; i++){
    ans = max(ans, dp[n][i]);
  }
  cout << ans;
  return 0;
}