题目大意

给定

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

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

文章操作

题目大意

思路

代码

相关推荐

评论

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