题目题解(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; vectorstring matrix(n); for (int i 0; i n; i) { cin matrix[i]; } vectorint 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(), greaterint()); 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; }