P11475 [COCI 2024/2025 #3] 红蓝牌 / Karte 详解
Cells
·
·
题解
这道题成功让我降智，胡了半天 DP，最后暴力过了……楼上金牌爷的 dinic 看的鄙人瑟瑟发抖，默默写下了暴力题解……
COCI 2024/2025 #3 Unofficial Mirror赛后总结。
思路
## Code
```c++
# include <bits/stdc++.h>
# define int LL
# define bpc __builtin_popcount
# define geti(x, i) (((x) >> (i)) & 1)
# define each1(i, x) for(auto (i) : (x))
# define each2(i, x) for(auto (&i) : (x))
# define rep(i, a, b) for(int i = (a); i <= (b); ++ i)
# define pre(i, a, b) for(int i = (a); i >= (b); -- i)
using namespace std;
using LL = long long;
const int N = 25;
int n, m, x, y, ans, val, cnt;
char ok[N][N];
signed main(){
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
cin >> n >> m >> x >> y;
rep(i, 1, n){
cin >> ok[i] + 1;
}
rep(s, 0, (1 << n) - 1){//枚举红牌
val = bpc(s) * (-x);//先把-X*r算出来
rep(i, 1, m){
cnt = 0;
rep(j, 0, n - 1){
if(geti(s, j)) cnt += (ok[j + 1][i] - '0');//如果可以和这一位组成好对
}
if(cnt - y > 0) val += cnt - y;//更新价值
}
ans = max(ans, val);
}
cout << ans;
return 0;
}
```
膜拜金牌爷%%%