好码风题解, 新手友好 | #小红的矩阵修改#

分析

非常有教育意义的状态压缩问题

注意到每个位置的状态有三个, 可以对应

并且发现行的数量非常少只有, 因此可以考虑三进制状态压缩

定义状态表示前列并且第列的状态是的最小代价, 状态转移递推即可

三进制状态的每一位获取方法是, 下一位获取方法是

• 首先预处理合法状态
• 初始化第一列状态
• 当前列的最小代价从前一列转移过来

代码实现

#include <bits/stdc++.h>

#define x first
#define y second

using namespace std;

typedef long long LL;
typedef pair<int, int> PII;

const int N = 5, M = 1010, MOD = 998244353;
const LL INF = 1e18;

int n, m;
string w[N];

int get(char c) {
    if (c == 'r') return 0;
    if (c == 'e') return 1;
    return 2;
}

int get_cost(int c, int s) {
    int cost = 0;
    for (int i = 0; i < n; ++i) {
        int v1 = get(w[i][c]);
        int v2 = s % 3;
        cost += v1 != v2;
        s /= 3;
    }
    return cost;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    cin >> n >> m;
    for (int i = 0; i < n; ++i) cin >> w[i];

    int s = pow(3, n);
    vector<vector<LL>> f(m + 1, vector<LL>(s, INF));

    vector<int> v;
    for (int i = 0; i < s; ++i) {
        int last = -1;
        bool ok = true;
        int tmp = i;
        for (int j = 0; j < n; ++j) {
            int cur = tmp % 3;
            if (cur == last) {
                ok = false;
                break;
            }
            last = cur;
            tmp /= 3;
        }
        if (ok) v.push_back(i);
    }

    for (int i : v) f[0][i] = get_cost(0, i);

    for (int j = 1; j < m; ++j) {
        for (int c : v) {
            int cost = get_cost(j, c);
            for (int p : v) {
                bool ok = true;
                int t1 = c, t2 = p;
                for (int i = 0; i < n; ++i) {
                    if (t1 % 3 == t2 % 3) {
                        ok = false;
                        break;
                    }
                    t1 /= 3, t2 /= 3;
                }
                if (ok) {
                    f[j][c] = min(f[j][c], f[j - 1][p] + cost);
                }
            }
        }
    }

    LL ans = INF;
    for (int i : v) ans = min(ans, f[m - 1][i]);

    cout << ans << '\n';
    return 0;
}