题解：P11475 [COCI 2024/2025 #3] 红蓝牌 / Karte

注意到数据范围很小，因此考虑暴力枚举选哪些红牌。

令

w_i

代表选了第

i

张蓝牌的话，会有哪些红牌和他产生贡献。为了方便，可以转化成二进制数存储。显然这个东西可以预处理出来。

设当前选的红牌集合为

i

（也是一个二进制数），可以枚举所有蓝牌。对于第

j

张蓝牌，如果该蓝牌的贡献

i \cap w_j

（实现时可以使用按位与运算）比

y

大，那么表示选第

j

张蓝牌是赚的。将其贡献累加到计数器上，最后减去

x \times \operatorname{popcount}(i)

就是答案。

时间复杂度

O(2^NM)

，代码实现如下：

CPP

#include<bits/stdc++.h>
using namespace std;
const int N=30; char s[N][N]; int w[N];
int main() {
    ios::sync_with_stdio(false),cin.tie(nullptr);
    int n,m,x,y,ans=0; cin>>n>>m>>x>>y;
    for(int i=1;i<=n;i++) cin>>(s[i]+1);
    for(int i=1;i<=m;i++) for(int j=1;j<=n;j++) if(s[j][i]-'0') w[i]|=(1<<(j-1));
    for(int i=0;i<(1<<n);i++) {
        int sum=-x*__builtin_popcount(i);
        for(int j=1;j<=m;j++) sum+=max(__builtin_popcount(i&w[j])-y,0);
        ans=max(ans,sum);
    }
    cout<<ans;
    return 0;
}

题解：P11475 [COCI 2024/2025 #3] 红蓝牌 / Karte

文章操作

相关推荐

评论

题解：P11475 [COCI 2024/2025 #3] 红蓝牌 / Karte