题解：P16304 [蓝桥杯 2026 省 Java C 组] 抽奖活动

HZY1618yzh · 2026-04-28 16:56:14 · 题解

题意

给出 n 数，可以执行 k 次操作，每次从剩余的球里选一个，保证左边的数的数量是右边的倍数，求最大拿到的数的和。

思路

由于 n 很小，可以考虑压装。dp_x 表示当前选择情况为 x 的最大权值。其中，x 的二进制位表示它对应的数是否被选择。
复杂度 \mathcal{O}(n2^n)。

代码

#include<bits/stdc++.h>
using namespace std;
int n,k,a[21],dp[2000000],mx;
int main(){
    //读入
    cin>>n>>k,memset(dp,-1,sizeof dp),dp[0]=0;
    for(int i=1;i<=n;i++) cin>>a[i];
    //枚举x
    for(int x=0;x<=(1<<n)-1;mx=max(mx,dp[x]),x++)
        if(int co=__builtin_popcount(x);dp[x]!=-1&&co<k){
            //判断是否能继续扩展
            for(int i=1,l=0,r;i<=n;i++)//扩展
                if(!(x&(1<<(i-1)))){//这个数没有被选上
                    r=n-co-l-1;//计算右边的数的个数
                    //满足要求就更新最大值
                    if(r&&!(l%r)) dp[x|(1<<(i-1))]=max(dp[x|(1<<(i-1))],dp[x]+a[i]);
                    l++;//左边的数字增加
                }
        }
    cout<<mx;//输出最大值
    return 0;
}