1391D. 505 状压dp

D
状压dp， 2000

题意

给出一个 $n\times m(n\le m)$ 的$01$矩阵，称任意一个边长为偶数的子正方形中1的个数为奇数的矩阵为好矩阵，求至少改多少个数，可以使其变为好矩阵。如果无论多少次操作都无法变为好矩阵，输出 $-1$ 。

思路

首先 $n\ge 4$ 的一定不行，因为 4 个 22 的矩阵个数为奇，则组成的 44 的矩阵个数为偶，于是考虑 $n\le 3$ 的。

1. $n=1$ 时，显然为 0 。
2. $n=2/3$ 时，设 $f[i][state]$ 表示前 $i$ 列满足条件且第 $i$ 列状态为 $state$ 的最小操作数。显然 $f[i][now]$ 只和 $f[i-1][pre]$ 有关，对于可以转移的状态，有 $f[i][now]=min(f[i][now],f[i-1][pre]+change(now,init))$ 。其中 $change(now,init)$ 即为初始的第 $i$ 列到状态为 $now$ 所需要改变的数。

所以现在只需要解决两个问题：如何判断 $now$ 和 $pre$ 之间能够转移，如何求 $change(now,init)$ 。
首先我们这样定义状态：对于 $n=3,state=a[1][i]\ast 4+a[2][i]\ast 2+a[3][i]$ ，对于 $n=2,state=a[1][i]\ast 2+a[2][i]$ ，第一个问题只需要判断2*2的矩阵中1的数量是否为奇数(若 $n=3$ 则需要判断2个2*2的矩阵)，第二个问题只需要判断 $now$ 和初始矩阵有几位不同 。

代码

int n, m;
int a[5][maxn];
int f[maxn][10];
int bit(int x, int y) {
    return (x >> y) & 1;
}
int change(int x, int y) {    //x 当前状态 y 目标状态
    int cnt = 0;
    for(int i = 0; i < 4; i++) {
        cnt += (bit(x, i) ^ bit(y, i));
    }
    return cnt;
}
int check2(int pre, int now) {
    int cnt = bit(pre, 1) ^ bit(pre, 0) ^ bit(now, 1) ^ bit(now, 0);
    return cnt;
}
int check3(int pre, int now) {
    int cnt1 = bit(pre, 1) ^ bit(pre, 0) ^ bit(now, 1) ^ bit(now, 0);
    int cnt2 = bit(pre, 1) ^ bit(pre, 2) ^ bit(now, 1) ^ bit(now, 2);
    return cnt1 && cnt2;
}
void solve() {
    memset(f, 0x3f, sizeof f);
    cin >> n >> m;
    if(n > 3) {
        cout << -1 << endl;
        return;
    }
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= m; j++) {
            char c;
            cin >> c;
            a[i][j] = c - '0';
        }
    }
    if(n == 1) {
        cout << 0 << endl;
        return;
    }
    if(n == 2) {
        for(int i = 0; i < 4; i++) {
            f[1][i] = change(i, a[1][1] * 2 + a[2][1]);
        }
        for(int j = 2; j <= m; j++) {
            for(int now = 0; now < 4; now++) {
                for(int pre = 0; pre < 4; pre++) {
                    if(check2(pre, now)) {
                        f[j][now] = min(f[j][now],
                        f[j-1][pre] + change(a[1][j]*2+a[2][j], now));
                    }
                }
            }
        }
    }
    if(n == 3) {
        for(int i = 0; i < 8; i++) {
            f[1][i] = change(i, a[1][1] * 4 + a[2][1] * 2 + a[3][1]);
        }
        for(int j = 2; j <= m; j++) {
            for(int now = 0; now < 8; now++) {
                for(int pre = 0; pre < 8; pre++) {
                    if(check3(now, pre)) {
                        f[j][now] = min(f[j][now],
                        f[j-1][pre] + change(now, a[1][j]*4+a[2][j]*2+a[3][j]));
                    }
                }
            }
        }
    }
    int ans = INF;
    for(int i = 0; i <= 7; i++) chmin(ans, f[m][i]);
    cout << ans << endl;
}
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
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74