解题思路:
自行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;
}
0.0分
0 人评分
C语言网提供由在职研发工程师或ACM蓝桥杯竞赛优秀选手录制的视频教程,并配有习题和答疑,点击了解:
一点编程也不会写的:零基础C语言学练课程
解决困扰你多年的C语言疑难杂症特性的C语言进阶课程
从零到写出一个爬虫的Python编程课程
只会语法写不出代码?手把手带你写100个编程真题的编程百练课程
信息学奥赛或C++选手的 必学C++课程
蓝桥杯ACM、信息学奥赛的必学课程:算法竞赛课入门课程
手把手讲解近五年真题的蓝桥杯辅导课程
发表评论 取消回复