P3392. 涂国旗

发表于 分类于 阅读次数： Waline： 本文字数： 225 阅读时长 ≈ 1 分钟

考点

  • 枚举

题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#include <bits/stdc++.h>

using namespace std;

char arr[51][51];

int N, M;

int cost(int bg, int ed, char c)
{
    int res = 0;
    for (int i = bg; i <= ed; ++i)
        for (int j = 1; j <= M; ++j)
        {
            if (arr[i][j] != c)
                ++res;
        }
    return res;
}

int main()
{
    cin >> N >> M;
    int ans = INT_MAX;
    for (int i = 1; i <= N; ++i)
        for (int j = 1; j <= M; ++j)
            cin >> arr[i][j];
    for (int i = 1; i <= N - 2; ++i)
    {
        int sum_w = cost(1, i, 'W');
        for (int j = N - 2; j >= 1; --j)
        {
            int sum_r = cost(N - j + 1, N, 'R');
            int sum_b = cost(i + 1, N - j, 'B');
            ans = min(ans, sum_w + sum_r + sum_b);
        }
    }
    cout << ans;
    return 0;
}

思路

假设一共有N行

白色的行最少有1行，最多有N-2行；红色的行最少也有1行，最多也有N-2行；白色与红色确认行数后，蓝色的行数也可以确认

所以直接令白色行数与红色行数执行双重循环的枚举，对比不同情况下的开销即可