Ciel有一个N*N的矩阵，每个格子里都有一个整数。

N是一个奇数，设X = (N+1)/2。Ciel每次都可以做这样的一次操作：他从矩阵选出一个X*X的子矩阵，并将这个子矩阵中的所有整数都乘以-1。

现在问你经过一些操作之后，矩阵中所有数的和最大可以为多少。

第一行为一个正整数N。

接下来N行每行有N个整数，表示初始矩阵中的数字。每个数的绝对值不超过1000。

输出一个整数，表示操作后矩阵中所有数之和的最大值。

数据规模与约定:

1 <= N <= 33，且N为奇数。

锦囊1

使用贪心。

锦囊2

令dp[i][j]表示矩阵中(i, j)位置的数是否要乘以-1。

注意dp[i][j]^dp[i][x]^dp[i][j+x] == 0,

dp[i][j]^dp[x][j]^dp[i+x][j] == 0 ;

所以只要确定了dp[x][j], dp[i][x], 就能将dp[i][j] 与 dp[i+x][j], dp[i][j+x]绑定起来了。

首先我们可以枚举dp[x][j]--可以通过枚举使用了哪些以(x, j)为左上角的矩形，那么这样，我们可以同时将dp[x][j+x]确定下来。

然后我们依次dp[j][x](j<x)--我们可以发现，对于每一个dp[j][x],其影响的只有dp[j][t](t<x)与dp[j][t+x]的关系以及dp[j+x][x]，所以任两个dp[j][x]是线性无关的。

那么我们就可以一个个枚举dp[j][x]是否为1，然后运用贪心。

蓝桥杯提高