301695: CF321D. Ciel and Flipboard
Memory Limit:256 MB
Time Limit:4 S
Judge Style:Text Compare
Creator:
Submit:0
Solved:0
Description
Ciel and Flipboard
题意翻译
在一张 $n\times n$($n$ 为奇数)的网格中,每个位置上有一个数 $a_{i,j}$($1\leq i,j\leq n$)。 设 $m=\frac{n+1}2$。现在你可以执行任意次操作:选定一个 $m\times m$ 的子矩阵,将子矩阵中的数全部变为其相反数。 求最终可能达到的、矩阵中所有数和的最大值。题目描述
Fox Ciel has a board with $ n $ rows and $ n $ columns, there is one integer in each cell. It's known that $ n $ is an odd number, so let's introduce ![](https://cdn.luogu.com.cn/upload/vjudge_pic/CF321D/6479833d305e8df8be298c6d130b2c56818252f6.png). Fox Ciel can do the following operation many times: she choose a sub-board with size $ x $ rows and $ x $ columns, then all numbers in it will be multiplied by -1. Return the maximal sum of numbers in the board that she can get by these operations.输入输出格式
输入格式
The first line contains an integer $ n $ , ( $ 1<=n<=33 $ , and $ n $ is an odd integer) — the size of the board. Each of the next $ n $ lines contains $ n $ integers — the numbers in the board. Each number doesn't exceed $ 1000 $ by its absolute value.
输出格式
Output a single integer: the maximal sum of numbers in the board that can be accomplished.
输入输出样例
输入样例 #1
3
-1 -1 1
-1 1 -1
1 -1 -1
输出样例 #1
9
输入样例 #2
5
-2 0 0 0 -2
0 -2 0 -2 0
0 0 -2 0 0
0 -2 0 -2 0
-2 0 0 0 -2
输出样例 #2
18