自动搬运

查看原文

来自洛谷，原作者为

	qiutian120529 勿以鳄小而喂之,无以鳝小而不喂 | ⎛⎝>⏝⏝<⎛⎝

搬运于2025-08-24 23:14:32，当前版本为作者最后更新于2025-08-18 18:49:26，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

洛谷 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;
}