【题目来源】
洛谷：P3392 涂条纹 - 洛谷 (luogu.com.cn)
【题目描述】
某国法律规定，只要一个由 \(N\times M\) 个小方块组成的旗帜符合如下规则，就是合法的图案。
- 从最上方若干行（至少一行）的格子全部是白色的；
- 接下来若干行（至少一行）的格子全部是蓝色的；
- 剩下的行（至少一行）全部是红色的；
现有一个棋盘状的布，分成了 \(N\) 行 \(M\) 列的格子，每个格子是白色蓝色红色之一，小 a 希望把这个布改成合法图案，方法是在一些格子上涂颜料，盖住之前的颜色。
小 a 很懒，希望涂最少的格子，使这块布成为一个合法的图案。
【输入】
第一行是两个整数 \(N,M\)。
接下来 \(N\) 行是一个矩阵，矩阵的每一个小方块是 W（白），B（蓝），R（红）中的一个。
【输出】
一个整数，表示至少需要涂多少块。
【输入样例】
4 5
WRWRW
BWRWB
WRWRW
RWBWR
【输出样例】
11
【解题思路】
【算法标签】
《洛谷 P3392 涂条纹》 #模拟# #枚举# #洛谷月赛#
【代码详解】
#include <bits/stdc++.h>
using namespace std;int main()
{int n, m, sum, ans = 1e9; // 定义变量：n-行数，m-列数，sum-临时和，ans-最小修改次数（初始设为极大值）int a1[55] = {0}, a2[55] = {0}, a3[55] = {0}; // 统计每行W/B/R的数量char tmp; // 临时存储每个字符// 输入行数n和列数mcin >> n >> m;// 统计每行W/B/R的数量for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) {cin >> tmp;if (tmp == 'W') a1[i]++; // 统计W的数量if (tmp == 'B') a2[i]++; // 统计B的数量if (tmp == 'R') a3[i]++; // 统计R的数量}// 枚举所有可能的划分方式for (int w = 1; w <= n - 2; w++) // W区域的行数（至少1行，最多n-2行）for (int b = 1; b <= n - w - 1; b++) // B区域的行数（剩余行中至少1行）{sum = 0; // 重置临时和// 计算W区域需要修改的次数（非W的字符数）for (int i = 1; i <= w; i++) sum += m - a1[i]; // 该行需要修改的字符数 = 总字符数 - W的数量// 计算B区域需要修改的次数（非B的字符数）for (int i = w + 1; i <= w + b; i++) sum += m - a2[i]; // 该行需要修改的字符数 = 总字符数 - B的数量// 计算R区域需要修改的次数（非R的字符数）for (int i = w + b + 1; i <= n; i++) sum += m - a3[i]; // 该行需要修改的字符数 = 总字符数 - R的数量// 更新最小修改次数if (sum < ans) ans = sum;}// 输出最小修改次数cout << ans;return 0;
}
【运行结果】
4 5
WRWRW
BWRWB
WRWRW
RWBWR
11