TopCoder 12875 PalindromeMatrix 题解

题意

给一个 \(n \times m\)\(01\) 矩阵,求至少将多少个格子取反才能使得至少有 \(r\) 行和 \(c\) 列是回文串。
\(2 \le n, m \le 14\)\(0 \le r \le n\)\(0 \le c \le m\)

做法

首先枚举有哪些行是回文串,然后考虑对列进行 DP。

容易发现一列一列地转移是不好转移的(因为你在考虑前面的时候无法知道后面填什么),所以考虑两列两列地转移。

设在当前枚举的条件下(有一些行是回文的情况下),

  • \(cost(i, j)\) 表示 \(i\) 列和第 \(m - i + 1\) 列中有 \(j\) 列是回文的最小代价(其中 \(0 \le j \le 2\)
  • \(f(i, j)\) 表示 \(i\) 列和后 \(i\) 列一共有 \(j\) 列是回文的最小代价

那么 \(f(i, j) = \min_{0 \le k \le 2} \left\{f(i - 1, j - k) + cost(i, k)\right\}\)。现在的问题是怎么算 \(cost\)

容易发现 \(s\) 是否回文只与 \(s_i\) 是否等于 \(s_{n - i + 1}\) 有关,所以在一个串中我们只用考虑 \(\frac n2\) 组对应字符内部的相等关系,而组与组之间是相互独立的。类似的,在一个矩阵中我们也只需要考虑 \(\frac{nm}{4}\) 组内部的关系。

所以我们枚举 \(i, j (1 \le i \le \frac n2, 1 \le j \le \frac m2)\),然后枚举 \((i, j)\) 这一组里 \(4\) 个格子每一个的状态,然后维护到对应的 \(cost\) 里就好了。

细节

在算 \(cost\) 时,由于 左边是回文右边是回文 都是 \(cost(i, 1)\),所以 可能 会出问题(看具体写法),可以考虑将其分开,状态变成 \(cost(i, 0/1/2/3)\)

另外,在维护到 \(cost\) 时,有一些细节,不过样例能查出来,留给读者自己调试。

代码

代码

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
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <string>
#include <vector>
using std::string;
using std::vector;
const int N = 14 + 5;
const int INF = 0x3f3f3f3f;
int a[N][N];
int n, m;
int f[N][N], cost[N][5];
void chkmin(int &x, int y) { if(y < x) x = y; }
class PalindromeMatrix {
public:
int minChange(vector<string> A, int rowCount, int columnCount) {
n = A.size(), m = A[0].size();
for(int i = 1; i <= n; i++) for(int j = 1; j <= m; j++) a[i][j] = A[i - 1][j - 1] - '0';
int U = (1 << n) - 1;
int ans = INF;
for(int s = 0; s <= U; s++) {
if(__builtin_popcount(s) < rowCount) continue;
memset(cost, 0, sizeof(cost));
memset(f, 0x3f, sizeof(f));
for(int i = 1; i <= n / 2; i++)
for(int j = 1; j <= m / 2; j++) {
int i_ = n - i + 1, j_ = m - j + 1;
int ri = s >> (i - 1) & 1, ri_ = s >> (i_ - 1) & 1;
int tmp[5] = {INF, INF, INF, INF};
for(int t = 0; t < 16; t++) {
int x = t & 1, y = t >> 1 & 1, z = t >> 2 & 1, w = t >> 3 & 1;
if(ri && (x != y)) continue;
if(ri_ && (z != w)) continue;
chkmin(tmp[(x == z) | ((y == w) << 1)], (x != a[i][j]) + (y != a[i][j_]) + (z != a[i_][j]) + (w != a[i_][j_]));
chkmin(tmp[((y == w) << 1)], (x != a[i][j]) + (y != a[i][j_]) + (z != a[i_][j]) + (w != a[i_][j_]));
chkmin(tmp[(x == z)], (x != a[i][j]) + (y != a[i][j_]) + (z != a[i_][j]) + (w != a[i_][j_]));
chkmin(tmp[0], (x != a[i][j]) + (y != a[i][j_]) + (z != a[i_][j]) + (w != a[i_][j_]));
}
cost[j][0] += tmp[0], cost[j][1] += tmp[1], cost[j][2] += tmp[2], cost[j][3] += tmp[3];
chkmin(cost[j][0], INF), chkmin(cost[j][1], INF), chkmin(cost[j][2], INF), chkmin(cost[j][3], INF);
}
f[0][0] = 0;
for(int i = 1; i <= m / 2; i++) for(int k = 0; k <= 3; k++)
for(int j = __builtin_popcount(k); j <= m; j++) chkmin(f[i][j], f[i - 1][j - __builtin_popcount(k)] + cost[i][k]);
for(int i = columnCount; i <= m; i++) chkmin(ans, f[m / 2][i]);
}
return ans;
}
};