题解：P10911 [蓝桥杯 2024 国 B] 数位翻转

· · 题解

P10911 题解

反转函数的写法

首先按题意把一个十进制数转为二进制，这里我们可以用短除法来解决。

int d[50],now=0;;
while(x>=1){
  d[++now]=x%2;
  x/=2;
}

然后我们可以使用 reverse() 函数来反转这个 d 数组。

reverse(d+1,d+now+1);

这个函数的使用方法就像 sort() 一样，此处不再赘述。

最后把这个二进制数再转回十进制。

int sum=0;
for(int i=1;i<=now;i++){
    if(d[i]) sum+=mem[i-1];
}

思路分析

我的第一个想法就时贪心，但又不能找到一个具有普遍性的贪心策略，于是想到了动态规划。

dp 数组的定义

先来看一下下面这张图片。

因为题目中提到了区间，所以我们先把这些区间画下来。

图中带有 f(x) 的区间为经过反转的区间，反之其他就是没有经过反转的。

观察发现，偶数个的区间都要经过反转。

因为经过反转的区间的两旁肯定是没有经过反转的区间。

当然，区间的长度可能为 0。

所以我们定义 dp_{i,j} 是以 a_i 结尾的，在第 j 个区间的最大和。

状态转移方程与目标

可推出：

dp_{i,j}=\max(dp_{i-1,j}+a_i,dp_{i-1,j-1}+a_i)(j \bmod 2=1)\\ dp_{i,j}=\max(dp_{i-1,j}+rev_i,dp_{i-1,j-1}+rev_i)(j \bmod 2=0)

解释：

对于 dp_{i,j} 可以继续保持在第 j 个区间上，同时也可以从第 j-1 个区间（上一个区间）转移过来。（代表开始反转或结束反转）

如果不能理解，可以再仔细想想 dp 数组的定义。

可推出答案 \max\limits_{i=1}^{2m+1}f_{n,i}。

解释：

最多有 2m+1 个区间但不代表取到最大和的答案已经在第 2m+1 个区间，甚至有可能答案就没有经过反转的区间或者只经过了几个。所以答案并不是 dp_{n,2m+1}。

代码

#include<iostream>
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=3005;
int a[N],dp[N][N],rev[N];
int f(int x){//反转函数
    int d[50],now=0;
    while(x>=1){
        d[++now]=x%2;
        x>>=1;
    }
    reverse(d+1,d+now+1);
    int sum=0;
    for(int i=1;i<=now;i++)  if(d[i]) sum+=1<<i-1;
    return sum;
}
signed main(){
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    for(int i=1;i<=n;i++) rev[i]=f(a[i]);
    for(int i=1;i<=n;i++){
        for(int j=1;j<=2*m+1;j++){
            int flag=a[i];
            if(j%2==0) flag=rev[i];
            dp[i][j]=max(dp[i-1][j],dp[i-1][j-1])+flag;//核心
        }
    }
    int ans=-1;
    for(int i=1;i<=2*m+1;i++){
        ans=max(ans,dp[n][i]);
    }
    cout<<ans;
}

都写的这么全了，给个赞再走吧 QwQ。