A1011. Spaced Out--Silver
编程题
普及+/提高
知识点
题目描述
Farmer John 想要拍摄一张他的奶牛吃草的照片挂在墙上。草地可以用一个 $N$ 行 $N$ 列正方形方格所组成的方阵表示（想象一个 $N \times N$ 的棋盘），其中 $2 \leq N \leq 1000$。在 Farmer John 最近拍摄的照片中，他的奶牛们太过集中于草地上的某个区域。这一次，他想要确保他的奶牛们分散在整个草地上。于是他坚持如下的规则：
- 没有两头奶牛可以位于同一个方格。
- 所有 $2 \times 2$ 的子矩阵（共有 $(N-1) \times (N-1)$ 个）必须包含恰好 2 头奶牛。
例如，这一放置方式是合法的：
```
CCC
...
CCC
```
而这一放置方式是不合法的，因为右下的 $2 \times 2$ 正方形区域仅包含 1 头奶牛：
```
C.C
.C.
C..
```
没有其他限制。你可以假设 Farmer John 有无限多的奶牛（根据以往的经验，这种假设似乎是正确的……）。
Farmer John 更希望某些方格中包含奶牛。具体地说，他相信如果方格 $(i, j)$ 中放有一头奶牛，照片的美丽度会增加 $a_{ij}$（$0 \leq a_{ij} \leq 1000$）单位。
求合法的奶牛放置方式的最大总美丽度。
- 没有两头奶牛可以位于同一个方格。
- 所有 $2 \times 2$ 的子矩阵（共有 $(N-1) \times (N-1)$ 个）必须包含恰好 2 头奶牛。
例如，这一放置方式是合法的：
```
CCC
...
CCC
```
而这一放置方式是不合法的，因为右下的 $2 \times 2$ 正方形区域仅包含 1 头奶牛：
```
C.C
.C.
C..
```
没有其他限制。你可以假设 Farmer John 有无限多的奶牛（根据以往的经验，这种假设似乎是正确的……）。
Farmer John 更希望某些方格中包含奶牛。具体地说，他相信如果方格 $(i, j)$ 中放有一头奶牛，照片的美丽度会增加 $a_{ij}$（$0 \leq a_{ij} \leq 1000$）单位。
求合法的奶牛放置方式的最大总美丽度。
输入格式
输入的第一行包含 $N$。以下 $N$ 行每行包含 $N$ 个整数。从上到下第 $i$ 行的第 $j$ 个整数为 $a_{ij}$ 的值。
输出格式
输出一个整数，为得到的照片的最大美丽度。
输入输出样例
输入 #1
4 3 3 1 1 1 1 3 1 3 3 1 1 1 1 3 3
输出 #1
22
说明/提示
## 说明/提示
在这个样例中，最大美丽度可以在如下放置方式时达到：
```
CC..
..CC
CC..
..CC
```
这种放置方式的美丽度为 $3 + 3 + 3 + 1 + 3 + 3 + 3 + 3 = 22$。
测试点性质：
- 测试点 2-4 满足 $N \le 4$。
- 测试点 5-10 满足 $N\le 10$。
- 测试点 11-20 满足 $N \le 1000$。
在这个样例中，最大美丽度可以在如下放置方式时达到：
```
CC..
..CC
CC..
..CC
```
这种放置方式的美丽度为 $3 + 3 + 3 + 1 + 3 + 3 + 3 + 3 = 22$。
测试点性质：
- 测试点 2-4 满足 $N \le 4$。
- 测试点 5-10 满足 $N\le 10$。
- 测试点 11-20 满足 $N \le 1000$。