Spaced Out

题目描述

农夫约翰想给在牧场里吃草的奶牛拍一张照片挂在墙上。牧场表示为一个 $N$ 行 $N$ 列的方格网（可以想象成一个 $N \times N$ 的棋盘），其中 $2 \leq N \leq 1000$。在约翰上一次拍的照片中，奶牛在牧场的某个区域里过于聚集。这一次，他希望确保奶牛在牧场中分布得更加均匀。因此他要求满足以下规则： 不允许两头奶牛放在同一个格子里。 每一个 $2 \times 2$ 的子方格（总共有 $(N-1) \times (N-1)$ 个）必须恰好包含 2 头奶牛。 例如，下面这种摆放是合法的： CCC ... CCC 而下面这种摆放是不合法的，因为包含右下角格子的那个 $2 \times 2$ 方形区域只包含 1 头奶牛： C.C .C. C.. 除此之外没有其他限制。你可以假设农夫约翰拥有无限多头奶牛可用（根据以往经验，这个假设似乎确实成立……）。 农夫约翰希望某些格子比其他格子更适合放奶牛。具体来说，当一头奶牛被放在格子 $(i, j)$ 时，照片的美感会增加 $a_{ij}$（$0 \leq a_{ij} \leq 1000$）个单位。请确定在满足摆放规则的前提下，照片总美感的最大可能值。

输入格式

第一行包含 $N$。接下来 $N$ 行每行包含 $N$ 个整数。从上往下数第 $i$ 行中的第 $j$ 个整数为 $a_{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 = 22$。 SCORING: 测试点 2-4 满足 $N \le 4$。 测试点 5-10 满足 $N\le 10$。 测试点 11-20 满足 $N \le 1000$。 题目来源：Hankai Zhang 和 Danny Mittal

标签: USACO|2021|Silver

来源

USACO|2021|Silver