小红的矩阵染色

思路

题目说，红色格子的正下方如果也是红色格子就得 1 分。换句话说，我们需要在同一列中找到尽可能多的"上下相邻红色对"。

先想一个简单问题——如果只有一列，全是 o，长度为 L，我花 l 个格子全染在一起，能得几分？

> l 个连续红色格子，相邻对数是 l - 1。

那如果这一列中间被 隔断了呢？比如 o o o o o，它就被拆成了两段：长度 2 和长度 3。跨段的格子之间被黑色隔开了，不可能形成相邻对，所以每一段是独立的。

这样问题就变成了：收集所有列中所有连续 o 段，每段长度为 L，从中选若干段，总共用不超过 k 个格子，使得得分最大。

对于一个长度为 L 的段，花 l 个格子（）可以得到 分。拆解一下边际收益：

  • 第 1 个格子：花 1 格，得 0 分（孤立一个红色没用）
  • 第 2 个格子：花 1 格，得 1 分（和第 1 个组成一对）
  • 第 3、4、... 个格子：每花 1 格，得 1 分

也就是说，启动一个段需要 2 格才能拿到第 1 分，之后每 1 格就多 1 分。那贪心策略就出来了：

> 应该优先把格子花在长段上，因为同样的"启动成本"（2 格换 1 分），长段能提供更多的"1 格换 1 分"的后续收益。

具体步骤

  1. 遍历每一列，提取所有连续 o 段，记录长度（长度 < 2 的没用，丢掉）
  2. 把所有段按长度从大到小排序
  3. 贪心分配 k 个格子：对每个段，用 个格子，得 分。剩余格子不足 2 就停止

代码

#include <bits/stdc++.h>
using namespace std;

int main() {
    int m, n, k;
    scanf("%d%d%d", &m, &n, &k);

    vector<string> grid(m);
    for (int i = 0; i < m; i++) {
        cin >> grid[i];
    }

    // 收集每列中所有连续 'o' 段的长度
    vector<int> segs;
    for (int j = 0; j < n; j++) {
        int cnt = 0;
        for (int i = 0; i < m; i++) {
            if (grid[i][j] == 'o') {
                cnt++;
            } else {
                if (cnt >= 2) segs.push_back(cnt);
                cnt = 0;
            }
        }
        if (cnt >= 2) segs.push_back(cnt);
    }

    // 长段优先
    sort(segs.begin(), segs.end(), greater<int>());

    int score = 0, rem = k;
    for (int len : segs) {
        if (rem < 2) break;
        int use = min(rem, len);
        score += use - 1;
        rem -= use;
    }

    printf("%d\n", score);
    return 0;
}

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int m = sc.nextInt(), n = sc.nextInt(), k = sc.nextInt();
        String[] grid = new String[m];
        for (int i = 0; i < m; i++) {
            grid[i] = sc.next();
        }

        List<Integer> segs = new ArrayList<>();
        for (int j = 0; j < n; j++) {
            int cnt = 0;
            for (int i = 0; i < m; i++) {
                if (grid[i].charAt(j) == 'o') {
                    cnt++;
                } else {
                    if (cnt >= 2) segs.add(cnt);
                    cnt = 0;
                }
            }
            if (cnt >= 2) segs.add(cnt);
        }

        segs.sort(Collections.reverseOrder());

        int score = 0, rem = k;
        for (int len : segs) {
            if (rem < 2) break;
            int use = Math.min(rem, len);
            score += use - 1;
            rem -= use;
        }

        System.out.println(score);
    }
}

import sys
input = sys.stdin.readline

m, n, k = map(int, input().split())
grid = [input().strip() for _ in range(m)]

segs = []
for j in range(n):
    cnt = 0
    for i in range(m):
        if grid[i][j] == 'o':
            cnt += 1
        else:
            if cnt >= 2:
                segs.append(cnt)
            cnt = 0
    if cnt >= 2:
        segs.append(cnt)

segs.sort(reverse=True)

score = 0
rem = k
for length in segs:
    if rem < 2:
        break
    use = min(rem, length)
    score += use - 1
    rem -= use

print(score)

const readline = require('readline');
const rl = readline.createInterface({ input: process.stdin });
const lines = [];
rl.on('line', line => lines.push(line));
rl.on('close', () => {
    const [m, n, k] = lines[0].split(' ').map(Number);
    const grid = [];
    for (let i = 1; i <= m; i++) grid.push(lines[i]);

    const segs = [];
    for (let j = 0; j < n; j++) {
        let cnt = 0;
        for (let i = 0; i < m; i++) {
            if (grid[i][j] === 'o') {
                cnt++;
            } else {
                if (cnt >= 2) segs.push(cnt);
                cnt = 0;
            }
        }
        if (cnt >= 2) segs.push(cnt);
    }

    segs.sort((a, b) => b - a);

    let score = 0, rem = k;
    for (const len of segs) {
        if (rem < 2) break;
        const use = Math.min(rem, len);
        score += use - 1;
        rem -= use;
    }

    console.log(score);
});

复杂度分析

  • 时间复杂度: ，其中 为段数，最多
  • 空间复杂度: ，存储网格和段列表

总结

这道题的核心是把二维矩阵问题转化成一维段的贪心选择。每一列被 * 隔开的连续 o 段是独立的，对于每个段花 l 个格子能得 l-1 分。由于"启动"一个段需要 2 个格子才能拿到第 1 分，所以我们应该优先把有限的 k 个格子投入到最长的段里，榨干每个段的收益后再开辟新段。排序 + 贪心分配，简洁明了。