练82.1 涂国旗

解题思路

枚举白蓝分界i和蓝红分界j，保证三段都非空。预处理每行改成W/B/R的代价前缀和，单次分界代价由三段相应前缀差相加，取最小。

正确性说明

依照上述推导，逐步维护已处理部分的有效状态。每一步都完成当前项的贡献且不改变已确定的次序，结束时输出的状态恰好对应题目要求。

易错点

一行必须统一颜色；不能漏掉至少一行红或蓝的要求。

复杂度

时间O(nm+n²)，空间O(n)。

参考代码（C++11）

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m;
    cin >> n >> m;
    vector<array<int, 3>> pre(n + 1);
    string colors = "WBR";
    for (int i = 1; i <= n; i++) {
        string s;
        cin >> s;
        for (int c = 0; c < 3; c++)
            pre[i][c] = pre[i - 1][c] + m - count(s.begin(), s.end(), colors[c]);
    }
    int best = INT_MAX;
    for (int i = 1; i <= n - 2; i++)
        for (int j = i + 1; j <= n - 1; j++)
            best = min(best, pre[i][0] + pre[j][1] - pre[i][1] + pre[n][2] - pre[j][2]);
    cout << best << "\n";
    return 0;
}