原题:Codeforces 321D. Ciel and Flipboard
题意: 的棋盘(nn为奇数),x=n+12x = \frac{n + 1}{2},每次可以将 的子矩阵取反,求棋盘的数字的最大值。

Description

小y是一个追求完美的女孩子。

这天,小y在玩一个大小为 的棋盘(nn为奇数),棋盘的每个格子上都有一个数。 小y发现这个棋盘里有一些负数,她想把负数都取反,从而使得这个棋盘的数字和最大。 但这时,小w突然阻止了她这个举动,并告诉她,每次只能选择一个 的子矩阵取反,其中, x=n+12x = \frac{n + 1}{2}

小y很不理解小w为什么这么说,但是为了展现出自己的水平,小y决定按照小w说的去做。 然后,小y发现自己不会做这题。但是由于小y只想把这个棋盘的数字和最大化,所以她向你请教了这 个问题,希望你能帮她解决。

input

第一行一个整数 nn。 接下来 nn 行,每行 nn 个整数,表示这个棋盘上的数字。

output

输出一个整数,表示经过若干次取反后棋盘的最大数字和。 样例输入

3
-1 -1 1
-1 1 -1
1 -1 -1

样例输出

9

数据范围

。 设 ww 为棋盘上的数字,则

Solution

结论题,我们用 v(a,b)v(a,b) 表示 (a,b)(a,b) 是否翻转( a,bxa,b\le x ),那么有 v(a,b) xor v(a,x) xor v(a,b+x)=0v(a,b) ~\text x\text o \text r~ v(a,x) ~\text x\text o \text r~ v(a,b+x)=0 。 列同样可以这样推:v(a,b) xor v(x,b) xor v(a+x,b)=0v(a,b)~\text{xor}~v(x,b)~\text{xor}~v(a+x,b)=0

我们枚举 (1~n, x),然后发现是左边的每一列是互相独立的,再枚举 (1~x-1,x),其余的点都可以推出来了。

时间复杂度:O(n22x)O(n^22^x)

Code

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
#include <cstdio>
#define re register int
#define rep(i,a,b) for(re i=(a);i<=(b);++i)
#define get(x,y) (v[x][y]?-c[x][y]:c[x][y])
inline int max(const int a, const int b) { return a>b?a:b;}

int n, x, ans=-0x3f3f3f3f, v[40][40], c[40][40];

inline int calc2(int a, int b, int d) {
v[a][b]=d, v[a][b+x]=d^v[a][x], v[a+x][b]=d^v[x][b];
v[a+x][b+x]=v[a+x][b]^v[a+x][x];
return get(a,b)+get(a+x,b)+get(a,b+x)+get(a+x,b+x);
}

inline int calc1(int b, int d) {
v[x][b]=d, v[x][b+x]=d^v[x][x];
int res = get(x,b)+get(x,b+x); //+ val(x,b),val(x,b+x)
rep(a,1,x-1) res += max(calc2(a,b,0),calc2(a,b,1)); //推三个角
return res;
}

inline int calc() {
int res=0;
rep(a,1,n) res += get(a, x);
rep(a,1,x-1)res += max(calc1(a,0),calc1(a,1)); //枚举(1~x-1,x) (互不影响)
return res;
}

int main() {
scanf("%d", &n);
x = (n+1)/2;
rep(i,1,n)rep(j,1,n) scanf("%d", &c[i][j]);
for(re S=0;S<(1<<x);++S) {
rep(i,1,x) v[i][x]=S>>(i-1)&1;
rep(i,x+1,n)v[i][x]=v[i-x][x]^v[x][x]; //枚举(1~n, x)
ans = max(ans, calc());
}
return printf("%d\n", ans), 0;
}