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