HJ172 小红的矩阵染色

• 题目
• 题解(23)
• 讨论(6)
• 排行

简单 通过率：31.75% 时间限制：1秒 空间限制：256M

知识点贪心

校招时部分企业笔试将禁止编程题跳出页面，为提前适应，练习时请使用在线自测，而非本地IDE。

描述

给定一个 n×mn×m 的矩阵，初始时部分格子已被染成黑色（用 ``**`` 表示），其余格子为空白（用 ``oo`` 表示）。

小红最多可以任选至多 kk 个空白格子，将其染成红色。计分规则如下：
∙ ∙ 若某个红色格子的正下方（同一列下一行）也是红色，则该格子贡献 11 分；
∙ ∙ 其他情况不计分。

请你帮小红计算，经过最优染色后，最多能获得多少分数。

输入描述：

第一行输入三个整数 n,m,k(1≦n,m≦103; 1≦k≦n×m)n,m,k(1≦n,m≦103; 1≦k≦n×m)，分别表示矩阵行数、列数及最多可染红的格子数量。
此后 nn 行，每行输入一个长度为 mm 的字符串 sisi​，描述第 ii 行初始状态：
∙ ∙ ``**`` 代表黑色格子，不能重新染色；
∙ ∙ ``oo`` 代表空白格子，可选择染为红色。

输出描述：

输出一个整数，表示小红通过最佳策略能够获得的最大分数。

示例1

输入：

4 4 3 *o*o oooo **** oooo

复制输出：

1

复制说明：

一种可行方案如下（``rr`` 为染成红色后的格子）： *r*o oroo **** oooo 红色格子共有 22 个，其中正下方同列的红色对数为 11，因此得分 11。

示例2

输入：

3 3 3 *o* *o* *o*

复制输出：

2

#include <iostream> #include <vector> #include <string> #include <algorithm> #include <functional> using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(NULL); int n, m; long long k; cin >> n >> m >> k; vector<string> matrix(n); for (int i = 0; i < n; ++i) { cin >> matrix[i]; } vector<int> chain_lengths; for (int j = 0; j < m; ++j) { int consecutive_white = 0; for (int i = 0; i < n; ++i) { if (matrix[i][j] == 'o') { consecutive_white++; } else { if (consecutive_white > 0) { chain_lengths.push_back(consecutive_white); } consecutive_white = 0; } } if (consecutive_white > 0) { chain_lengths.push_back(consecutive_white); } } sort(chain_lengths.begin(), chain_lengths.end(), greater<int>()); long long score = 0; for (int len : chain_lengths) { if (k <= 0) break; long long to_color = min((long long)len, k); k -= to_color; if (to_color > 1) { score += to_color - 1; } } cout << score << endl; return 0; }