#P7301. [USACO21JAN] Spaced Out S

[USACO21JAN] Spaced Out S

题目描述

Farmer John 想要拍摄一张他的奶牛吃草的照片挂在墙上。草地可以用一个 NNNN 列正方形方格所组成的方阵表示(想象一个 N×NN \times N 的棋盘),其中 2N10002 \leq N \leq 1000。在 Farmer John 最近拍摄的照片中,他的奶牛们太过集中于草地上的某个区域。这一次,他想要确保他的奶牛们分散在整个草地上。于是他坚持如下的规则:

  • 没有两头奶牛可以位于同一个方格。
  • 所有 2×22 \times 2 的子矩阵(共有 (N1)×(N1)(N-1) \times (N-1) 个)必须包含恰好 2 头奶牛。

例如,这一放置方式是合法的:

CCC
...
CCC

而这一放置方式是不合法的,因为右下的 2×22 \times 2 正方形区域仅包含 1 头奶牛:

C.C
.C.
C..

没有其他限制。你可以假设 Farmer John 有无限多的奶牛(根据以往的经验,这种假设似乎是正确的……)。

Farmer John 更希望某些方格中包含奶牛。具体地说,他相信如果方格 (i,j)(i, j) 中放有一头奶牛,照片的美丽度会增加 aija_{ij}0aij10000 \leq a_{ij} \leq 1000)单位。

求合法的奶牛放置方式的最大总美丽度。

输入格式

输入的第一行包含 NN。以下 NN 行每行包含 NN 个整数。从上到下第 ii 行的第 jj 个整数为 aija_{ij} 的值。

输出格式

输出一个整数,为得到的照片的最大美丽度。

4
3 3 1 1
1 1 3 1
3 3 1 1
1 1 3 3
22

提示

在这个样例中,最大美丽度可以在如下放置方式时达到:

CC..
..CC
CC..
..CC

这种放置方式的美丽度为 3+3+3+1+3+3+3+3=223 + 3 + 3 + 1 + 3 + 3 + 3 + 3 = 22

测试点性质:

  • 测试点 2-4 满足 N4N \le 4
  • 测试点 5-10 满足 N10N\le 10
  • 测试点 11-20 满足 N1000N \le 1000

供题:Hankai Zhang,Danny Mittal