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

· · 题解

题目大意

给定 n 个数 A_i，每个数我们都将其视为一个 32 位的二进制数。你可以进行 m 次操作，每次选择任意一个数将其循环左移一次。不超过 m 次操作后，n 个数的和最大是多少。

思路

鄙人动态规划不熟，在和机房同学交流后确定是考察动态规划，考虑如何转移。

因为每个数都是 32 位的二进制数，所以每个数总共只有 32 种变化，那么问题就转化成：从 1 到 n，对于每个 A_i 取一种变化，使得在 m 的代价之内和最大。这其实非常像背包 dp。

设 a_{i,j} 为 A_i 循环左移 j 次得到的数，则状态转移方程如下：

dp_{i,j} = \max(dp_{i,j},dp_{i-1,j-k}+a_{i,k})

接下来考虑如何求解 a_{i,j} 数组。因为每次循环左移可以理解为先左移一位，再或上最高位，即 (A << 1) | (A >> 31)，所以我们可以在输入时就预处理好 a_{i,j} 数组。

代码

实现的一些小细节都在注释里面，警钟长鸣。

#include <bits/stdc++.h>
using namespace std;
int n,m;
unsigned int a[1003][33];
long long dp[1003][1003];
int main(){
    cin >> n >> m;
    for(int i=1;i<=n;i++){
        unsigned A; // 注意要非负 防止位运算后成负数 同理 a[i][j] 也要非负
        cin >> A;
        for(int j=0;j<=31;j++)
        {
            a[i][j] = A;
            A = (A << 1) | (A >> 31);
        } // 记得考虑不操作的情况
    }
    for(int i=1;i<=n;i++)
        for(int j=0;j<=m;j++) 
            for(int k=0;k<=min(31,j);k++) // j-k 不能是负数 
                dp[i][j] = max(dp[i][j],dp[i-1][j-k]+a[i][k]);
    long long ans = -1;
    for (int i=0;i<=m;i++) 
        ans = max(ans,dp[n][i]); 
    cout << ans;
    return 0;
}