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

解题思路:
自行dp出来了

将区间分为翻转区间与非翻转区间，区间总数是2*m+1

数组元素分为状态翻转0与未翻转1

它们之间的相互切换，转移为区间数+1

堆积与rotate间的差值和为最优解

注意事项:

参考代码:

#include<bits/stdc++.h>

using namespace std;

const int N = 1005;

inline int rotate(int x){

    int b[40],k=0,sum=0,i;

    while(x>0){

        b[k++]=x%2;

        x/=2;

    }

    for(i=0;i<k/2;i++) swap(b[i],b[k-1-i]);

    for(i=k-1;i>=0;i--) sum=2*sum+b[i];

    return sum;

}

int main(){

    long long dp[N][N][2]={0},t=0,sum=0,d;int i,j,u1,u2,a[N],n,m,k;

    cin>>n>>m;

    for(i=0;i<n;i++){ 

        cin>>u1; u2=rotate(u1),d=u2-u1; sum+=u1;

        dp[i][1][1]=max(d,dp[i][1][1]);

        if(i>0){

            for(k=1;k<m;k++){

                dp[i][k][1]=max(dp[i][k][1],dp[i-1][k][1]+d);

                dp[i][k][0]=max(dp[i][k][0],dp[i-1][k][0]);

                dp[i][k+1][1]=max(dp[i][k+1][1],dp[i-1][k][0]+d);

                dp[i][k+1][0]=max(dp[i][k+1][0],dp[i-1][k][1]);

            }

            dp[i][k][1]=max(dp[i][k][1],dp[i-1][k][1]+d);

            dp[i][k][0]=max(dp[i][k][0],dp[i-1][k][0]);

        }

    }

    for(i=0;i<n;i++) for(j=1;j<=m;j++) t=max(t,max(dp[i][j][0],dp[i][j][1]));

    cout<<sum+t; 

    return 0;

}