题解：P5985 [PA 2019] Muzyka pop

qnqfff · 2026-01-23 22:34:38 · 题解

唐题。

思路

首先对于 b 的最高位，要么全是 0 或 1，要么一定存在一个分界点 k\in[l,r) 满足 b_l 到 b_k 是 0，b_{k+1} 到 b_r 是 1，且之后左右两边变成了独立的两个问题，所以设 f_{u,l,r,o} 表示考虑到第 u 位目前 [l,r] 全填的一样的，是否卡到上界，直接数位 dp 即可。

代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
char buf[1<<23],*p1=buf,*p2=buf;
int read(){int p=0,flg=1;char c=getchar();while(c<'0'||c>'9'){if(c=='-') flg=-1;c=getchar();}while(c>='0'&&c<='9'){p=p*10+c-'0';c=getchar();}return p*flg;}
int n,m,a[210],f[210][210][210][2],vis[210][210][210][2];
signed main(){
    n=read();m=read();for(int i=1;i<=n;i++) a[i]=a[i-1]+read();
    function<int(int,int,int,int)>dfs=[&](int u,int l,int r,int f1)->int{
        if(!~u) return l==r?0:-1e18;if(vis[u][l][r][f1]) return f[u][l][r][f1];
        int res=dfs(u-1,l,r,f1&(m>>u&1^1));
        if(!f1||m>>u&1){
            res=max(res,dfs(u-1,l,r,f1&(m>>u&1))+a[r]-a[l-1]);
            for(int k=l;k<r;k++) res=max(res,dfs(u-1,l,k,f1&(m>>u&1^1))+dfs(u-1,k+1,r,f1&(m>>u&1))+a[r]-a[k]);
        }vis[u][l][r][f1]=1;return f[u][l][r][f1]=res;
    };cout<<dfs(60,1,n,1);
    return 0;
}