题目 3293: 蓝桥杯2024年第十五届决赛真题-数位翻转

https://www.dotcpp.com/oj/problem3293.html

题目描述

小明创造了一个函数 f(x) 用来翻转 x 的二进制的数位（无前导 0）。比如f(11) = 13，因为 11 = (1011)₂，将其左右翻转后，变为 13 = (1101)₂；再比如f(3) = 3，f(0) = 0，f(2) = f(4) = f(8) = 1 等等。

小明随机出了一个长度为 n 的整数数组 {a1, a2, ..., an}，他想知道，在这个数组中选择最多 m 个不相交的区间，将这些区间内的数进行二进制数位翻转（将ai 变为 f(ai)）后，整个数组的和最大是多少？

输入格式

输入共 2 行。

第一行为两个正整数 n, m。

第二行为 n 个由空格分开的整数 a1, a2, ..., an。

输出格式

输出共 1 行，一个整数表示答案。

样例输入

5 3
11 12 13 14 15

样例输出

67

提示

【样例说明 1】只翻转 a1，和为 13 + 12 + 13 + 14 + 15 = 67。

再比如：

【样例输入 2】6 223 8 11 19 16 35

【样例输出 2】134

【样例说明 2】翻转区间 [a3, a4] 和 [a6]，和为 23 + 8 + 13 + 25 + 16 + 49 = 134。

【评测用例规模与约定】

对于 20% 的评测用例，保证 n, m ≤ 20。

对于 100% 的评测用例，保证 n, m ≤ 1000，0 ≤ a_i ≤ 10⁹。

 1 #include<iostream>
 2 #include<algorithm>
 3 using namespace std;
 4 typedef long long ll;
 5 const int maxn=1e3+100;
 6 ll a[maxn];
 7 ll b[maxn];
 8 ll tmp[100000];
 9 ll dp[maxn][maxn][2];//1是这个变化，0是不变化 
10 ll get(ll x){
11     
12     ll ans=0,p=1,cnt=0;
13     while(x){
14         tmp[++cnt]=x%2;
15         x/=2;
16     }
17     for(int i=cnt;i>=1;i--){
18         ans=ans+p*(tmp[i]);
19         p=p*2ll;
20     }
21     return ans;
22 }
23 int main(){
24     int n,m;
25     cin>>n>>m;
26     for(int i=1;i<=n;i++){
27         cin>>a[i];
28         b[i]=get(a[i]);
29     }
30     for(int i=1;i<=n;i++){
31         dp[i][0][0]=dp[i-1][0][0]+a[i];
32         for(int j=1;j<=m;j++){
33             dp[i][j][0]=max(dp[i-1][j][0],dp[i-1][j][1])+a[i];
34             dp[i][j][1]=max(dp[i-1][j-1][0]+b[i],dp[i-1][j][1]+b[i]);
35         }
36     }
37     ll ans=0;
38     for(int j=0;j<=m;j++){
39         ans=max(ans,max(dp[n][j][0],dp[n][j][1]));
40     }
41     cout<<ans<<endl;
42 }