小红的矩阵染色

思路

题目在说什么？给你一个 的矩阵，里面有黑色格子（*）和白色格子（o），你最多可以把 个白色格子染成红色。得分规则：一个红色格子的正下方也是红色时，这个格子贡献 1 分。问最多能得几分？

换句话说，我们要在矩阵里选一些白色格子染红，让红色格子在纵向上尽量连续。

那怎么想这道题呢？

关键观察

首先，得分只和同一列中相邻的红色格子有关。横向相邻没有贡献，所以我们可以逐列独立分析。

对于每一列，黑色格子把白色格子分成了若干段连续的白色区间。比如一列是 o o * o o o，那就被分成长度为 2 和长度为 3 的两段。

如果我们在某段长度为 的连续白色区间中选了 个格子来染红（），最优的做法当然是选连续的 个，这样得分是 。

那问题就变成了：我们有若干段，每段长度为 ，用至多 个格子分配到这些段里，最大化总得分。

贪心策略

想想看，在一段里染 个格子，花费 ，收益 。那么：

  • 开始一段新的区间：前 2 个格子才产生 1 分，每分的代价是 2
  • 继续延伸已有的区间：每多 1 个格子就多 1 分，每分的代价是 1

所以策略很清晰：优先把长的段填满，因为长的段能提供更多"代价 1"的延伸机会。启动一个新段的代价是 2 格子换 1 分，不如在已有的段里继续延伸划算。

具体做法：

  1. 遍历每一列，找出所有长度 的连续白色段
  2. 按长度从大到小排序
  3. 贪心地从最长的段开始，尽量填满，直到 个格子用完

如果最后只剩 1 个格子，没法产生任何得分（需要至少 2 个连续红色格子才有分），直接丢弃即可。

代码

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

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

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

    vector<int> segs;
    for(int j = 0; j < m; j++){
        int cnt = 0;
        for(int i = 0; i < n; 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 remaining = k;
    long long score = 0;
    for(int len : segs){
        if(remaining <= 1) break;
        int use = min(remaining, len);
        if(use >= 2){
            score += use - 1;
            remaining -= use;
        }
    }

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

import java.util.*;

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

        List<Integer> segs = new ArrayList<>();
        for (int j = 0; j < m; j++) {
            int cnt = 0;
            for (int i = 0; i < n; 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 remaining = k;
        long score = 0;
        for (int len : segs) {
            if (remaining <= 1) break;
            int use = Math.min(remaining, len);
            if (use >= 2) {
                score += use - 1;
                remaining -= use;
            }
        }

        System.out.println(score);
    }
}

import sys
input = sys.stdin.readline

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

segs = []
for j in range(m):
    cnt = 0
    for i in range(n):
        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)

remaining = k
score = 0
for length in segs:
    if remaining <= 1:
        break
    use = min(remaining, length)
    if use >= 2:
        score += use - 1
        remaining -= 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 [n, m, k] = lines[0].split(' ').map(Number);
    const grid = [];
    for (let i = 0; i < n; i++) grid.push(lines[i + 1]);

    const segs = [];
    for (let j = 0; j < m; j++) {
        let cnt = 0;
        for (let i = 0; i < n; 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 remaining = k;
    let score = 0;
    for (const len of segs) {
        if (remaining <= 1) break;
        const use = Math.min(remaining, len);
        if (use >= 2) {
            score += use - 1;
            remaining -= use;
        }
    }

    console.log(score);
});

复杂度分析

  • 时间复杂度：，其中 是白色段的数量（最多 ），排序占
  • 空间复杂度：，存储矩阵和段列表

总结

这道题的核心在于把二维矩阵的问题拆解成一维的列段问题。因为得分只和纵向相邻有关，横向完全独立，所以每列单独处理就行。找到所有白色连续段之后，就是一个经典的贪心：长的段性价比更高（延伸代价低），优先填满长段。整个思路从"观察得分规则"到"逐列拆段"再到"排序贪心"，一步步推导下来还是比较自然的。