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

解题思路:

这道题目可以用动态规划来解决，主要步骤如下：

1.定义状态：

dp[i][j][0] 表示前 i 个数中恰好选择 j 个区间，且第 i 个数没有翻转时的最大和。

dp[i][j][1] 表示前 i 个数中恰好选择 j 个区间，且第 i 个数已经翻转时的最大和。

2.状态转移方程：

dp[i][0][0] = dp[i-1][0][0] + a[i]：表示没有选择任何区间时，第 i 个数不翻转的最大和。

dp[i][j][0] 表示第 i 个数不翻转的情况下，选择了 j 个区间后的最大和。

那么第i-1个数有以下两种情况:

  1.第 i -1个数不翻转，那么dp[i][j][0]=dp[i-1][j][0]+ a[i]；

  2.第 i 个数翻转，那么dp[i][j][0]=dp[i-1][j][1]+ a[i]；

所以 dp[i][j][0]=max(dp[i-1][j][0], dp[i-1][j][1]) + a[i]；

dp[i][j][1] 表示第 i 个数翻转的情况下，选择了 j 个区间后的最大和，可以从前一个数的状态转移过来（此时多了一个区间）。

那么第i-1个数也有以下两种情况:

  1.第 i -1个数不翻转，因为第i个数翻转且第i-1个数不翻转，所以此时的区间不能连起来了，那么dp[i][j][0]=dp[i-1][j-1][0]+ b[i]；

  2.第 i 个数翻转，因为第i个数翻转且第i-1个数翻转，所以此时的区间能连起来了，那么dp[i][j][0]=dp[i-1][j][1]+ a[i]；

所以 dp[i][j][1]=max(dp[i-1][j-1][0], dp[i-1][j][1]) + b[i]；

3.初始化：

dp[i][0][0] 表示没有选择任何区间时的和。

注意事项:

1.注意这是区间，比如第5个数和第4个数翻转是算一个区间的，可以连起来，而不是两个区间!!!

2.f函数的解释:
while (x > 0)：当 x 大于 0 时，循环继续。

res = (res << 1) | (x & 1);：将 x 的最后一位加到 res 的最后，并将 res 左移一位。这一步的作用是将 x 的最后一位添加到 res 的二进制末尾。

x >>= 1;：将 x 右移一位，以便在下一次循环时处理下一位。

参考代码:

#include#includeusing namespace std;
typedef long long ll;
const int maxn=1e3+100;
ll a[maxn];
ll b[maxn];
ll tmp[100000];
ll dp[maxn][maxn][2];//1是这个变化，0是不变化 
ll f(ll x){
   
    ll res = 0;
    while (x > 0) {
        res = (res << 1) | (x & 1);// 将x的最后一位加到res的最后
        x >>= 1;// 将x右移一位
    }
    return res;
}
int main(){
    int n,m;
    cin>>n>>m;
    for(int i=1;i>a[i];
        b[i]=f(a[i]);
    }
    for(int i=1;i<=n;i++){
        dp[i][0][0]=dp[i-1][0][0]+a[i];
        for(int j=1;j<=m;j++){
            dp[i][j][0]=max(dp[i-1][j][0],dp[i-1][j][1])+a[i];
            dp[i][j][1]=max(dp[i-1][j-1][0],dp[i-1][j][1])+b[i];
        }
    }
    ll ans=0;
    for(int j=0;j<=m;j++){
        ans=max(ans,max(dp[n][j][0],dp[n][j][1]));
    }
    cout<<ans<<endl;
}