P6903: 美丽的照片
传统题
1.000s
时间限制
256MB
内存限制
1 提交
1 解决
【题目描述】
【问题描述】
Farmer John
想要拍摄一张他的奶牛吃草的照片挂在墙上。草地可以用一个 N
行 N 列正方形方格所组成的方阵表示（想象一个 N×N 的棋盘），其中 2≤N≤1000。在 Farmer John
最近拍摄的照片中，他的奶牛们太过集中于草地上的某个区域。这一次，他想要确保他的奶牛们分散在整个草地上。于是他坚持如下的规则：
1、没有两头奶牛可以位于同一个方格。
2、所有 2×2
的子矩阵（共有 (N−1)×(N
−1)个）必须包含恰好 2 头奶牛。
例如，这一放置方式是合法的：
CCC
...
CCC
而这一放置方式是不合法的，因为右下的 2×2
正方形区域仅包含 1 头奶牛：
C.C
.C.
C..
没有其他限制。你可以假设 Farmer John
有无限多的奶牛（根据以往的经验，这种假设似乎是正确的……）。
Farmer John
更希望某些方格中包含奶牛。具体地说，他相信如果方格 (i,j) 中放有一头奶牛，照片的美丽度会增加 aij（0≤aij≤1000
）单位。
求合法的奶牛放置方式的最大总美丽度。
【
输入格式】
（从终端/
标准输入读入）：
输入的第一行包含 N
。以下 N
行每行包含 N 个整数。从上到下第 i 行的第 j 个整数为 aij 的值。
【
输出格式】
（输出至终端/
标准输出）：
输出一个整数，为得到的照片的最大美丽度。
【
输入样例】
：
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
。
【
测试点性质】
：
测试点 2-4
满足 N≤4。
测试点 5-10
满足 N≤10。
测试点 11-20
满足 N≤1000。