526互联

ICPC2022Xian B Cells Coloring 题解

发布时间 2023-12-08 00:05:46作者: Martian148

Link

[ICPC2022Xian B Cells Coloring](ICPC2022Xian B Cells Coloring)

Question

感觉这种解法会被Hack,欢迎讨论

给出一个 \(n\times m\) 的网格，有些格子堵住了，有些格子空着，要选 \(k+1\) 种颜色给空着的格子染色，颜色编号 \(0,1,2,\cdots, k\) ，对于非 \(0\) 的颜色每行每列只能出现一次，定义 \(z\) 表示染成 \(0\) 颜色的格子数量，\(c,d\) 是给定的两个数，需要最小化 \(ck+dz\)

Solution

这个问题可以转化为，把一些空着的格子分成两类

  • 第一类有多组，在同一组的格子在一行一列只能选一个，显然，组数就是 \(k\)
  • 第二类是第一类种剩下的那个，第二类的数量就是 \(z\)

我们可以暴力枚举 \(k\) ，然后求出 \(z\)

考虑极端的情况，\(k\times k\) ，可以构造出一种可行方案

1 2 3 4 5
2 3 4 5 1
3 4 5 1 2
4 5 1 2 3
5 1 2 3 4

对于不是方阵，我们可以把方阵 "拉开"，保证每行每列能有 \(k\) 个非 \(0\) 数字

比如

..#..#
...#..
#.....
.....#
#....#

1 2 # 4 5 #
2 3 4 5 # 1
# 4 5 1 2 3 
4 5 1 2 3 #
# 1 2 3 4 #

所以如果一行的空格数是 \(x\) ，那么需要补充 \(0\) 的个数就是 \(\max(x-k,0)\)

列也是一样，枚举 \(k\)，刷最小值即可

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int maxn=305;
int n,m,c,d,a[maxn],b[maxn];
char s[maxn][maxn];
void solve() {
    cin >> n >> m >> c >> d;
    for (int i = 0; i < n; i++)cin >> s[i];
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (s[i][j] == '.') {
                a[i]++;
                b[j]++;
            }
        }
    }
    int k = max(*max_element(a, a + n), *max_element(b, b + m));
    int ans = c * k;
    for (int i = k - 1; i >= 0; i--) {
        int cnt1 = 0;
        for (int j = 0; j < n; j++)
            cnt1 += max(0LL, a[j] - i);
        int cnt2 = 0;
        for (int j = 0; j < m; j++)
            cnt2 += max(0LL, b[j] - i);
        ans = min(ans, max(cnt2, cnt1) * d + c * i);
    }
    cout << ans << endl;
}
signed main(){
    solve();
}