题解 | #小红的矩阵染色#

本题的核心在于如何分配有限的着色预算 ，以最大化垂直相邻红色格子对的数量。

1. 得分机制

• 得分条件：只有当一个红色格子的下方也是红色格子时，该格子才计 1 分。这意味着，在一个连续垂直长度为 的红色色块中，贡献的分数为 。

• 空间限制：黑色格子（*）是天然的屏障，红色格子只能填充在白色格子（o）的位置。因此，每一列会被黑色格子分割成若干个相互独立、垂直连续的白色段。

• 目标函数：设我们选择了 个连续段，在第 个段中染了 个格子（），则总得分为：

  

  这里的 即为消耗的涂染次数，最大为 。

2. 潜在难点

• 不能跨列计算得分。
• 不能跨越黑色格子计算得分。
• 由于 的存在，每开启一个新的连续段，都会导致潜在的“得分损失”（即 个格子只能拿到 分）。

贪心算法 (Greedy Strategy)

1. 核心思路

为了使总分 最大化，在 （涂染总数）固定的情况下，我们的目标是最小化 （使用的连续段数量）。

为了用最少的段数装下 个红色格子，我们应该优先选择长度较长的白色连续段进行填充。

2. 策略证明

假设有两个白色段，长度分别为 和 ，且 。

• 如果我们有 个格子要填：
  • 若 ，只需 1 个段，得分 。
  • 若 且 ，则需 2 个段，得分 。
• 显然，段数越少，得分越高。优先填满长段能更快地消耗 ，从而推迟或避免开启新的段。

3. 特殊情况处理

• 如果 超过了矩阵中所有白色格子的总数 ，则 应取 。
• 如果 或矩阵全为黑格，得分为 0。
• 即使某个段只能填充 1 个格子（导致该段得分 ），只要 还有剩余，填充它也不会减少当前已有的总分，但在本题逻辑下，我们会尽量避免这种情况。

代码实现

#include <bits/stdc++.h>
#include <queue>
using namespace std;
using ll = long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m, k;
    cin >> n >> m >> k;
    vector<string> s(n);
    for (int i = 0; i < n; i++)
        cin >> s[i];

    int W = 0;
    priority_queue<int> segments;

    for (int c = 0; c < m; c++) {
        int cur = 0;
        for (int r = 0; r < n; r++) {
            if (s[r][c] == 'o') {
                cur++;
                W++;
            } else if (s[r][c] == '*') {
                if (cur > 0)
                    segments.push(cur);
                cur = 0;
            }
        }
        if (cur > 0)
            segments.push(cur);
    }

    k = min(k, W);
    if (k <= 0) {
        cout << 0 << endl;
        return 0;
    }

    int usedCells = 0;
    int cnt = 0;

    while (!segments.empty()) {
        cnt++;
        usedCells += segments.top();
        segments.pop();
        if (usedCells >= k)
            break;
    }

    int ans = k - cnt;
    cout << ans << endl;
}