Ciel and Flipboard
一道好题，很有思维难度。
首先，我们发现 \(n\) 很小，所以对于一些位置应该是可以枚举的，再通过一些限制来确定其他位置。
对于操作的矩阵 \(m * m\)，我们发现中间一行必会被操作，而 \(i\) 和 \(i + m\) 行有且仅有一个被操作，那么设 \(f_{i,j}\) 表示 \(i\) 行 \(j\) 列的点是否操作，那么 \(f_{i,j} \oplus f_{m,j} \oplus f_{i + m,j} = 0\)，列同理。
这样，我们只需要确定四分之一个矩形的状态即可，但这样还不够，因为 \(n \le 33\)，猜想一下时间复杂度应该为 \(O(2^m m^k)\)，那么我们考虑如何只确定一行，我们发现只要确定第 \(m\) 行，其他位置的状态是独立的，可以直接一位一位贪心，这样这题就解决了，时间复杂度\(O(2^mm^2)\)。
Code
#include<bits/stdc++.h>
#define LL long long
#define eb emplace_back
#define IN inline
using namespace std;
const int N = 50, inf = 1e9;
int n, m, a[N][N], b[N];
IN int read() {
int t = 0,res = 0; char ch = getchar();
for (; !isdigit(ch); ch = getchar()) t |= (ch == '-');
for (; isdigit(ch); ch = getchar()) res = (res << 3) + (res << 1) + (ch ^ 48);
return t ? -res : res;
}
int work() {
int res = 0;
for (int i = m + 1; i <= n; i++) b[i] = b[m] ^ b[i - m];
for (int i = 1; i <= n; i++) res += b[i] ? -a[i][m] : a[i][m];
for (int i = 1; i < m; i++) {
int mz = -inf;
for (int j = 0; j < 2; j++) {
int tmp = 0;
for (int k = 1; k < m; k++) {
int fl1 = b[k] ? -1 : 1, fl2 = j ? -1 : 1, fl3 = j ^ b[m + k] ? -1 : 1;
int z = a[k][i] + a[k][i + m] * fl1 + a[k + m][i] * fl2 + a[k + m][i + m] * fl3;
if (z < 0) z = -z;
tmp += z;
}
int fl1 = j ? -1 : 1, fl2 = j ^ b[m] ? -1 : 1;
mz = max(mz, tmp + fl1 * a[m][i] + fl2 * a[m][i + m]);
}
res += mz;
}
return res;
}
int main() {
n = read(), m = n / 2 + 1;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
a[i][j] = read();
int ans = -inf;
for (int i = 0; i < (1 << m); i++) {
for (int j = 1; j <= m; j++) b[j] = (i >> j - 1) & 1;
ans = max(ans, work());
}
printf("%d\n", ans);
}