OI题库

【问题描述 】

NOI2008公司最近推出了一款新的坦克游戏。在游戏中，你将操纵一辆坦克，在一个 N × M 的区域中完成一项任务。在此的区域中，将会有许多可攻击的目标，而你每摧毁这样的一个目标，就将获得与目标价值相等的分数。只有获得了最高的分数，任务才算完成。同时，为了增加游戏的真实性和难度，该游戏还做了以下的限制：

• 坦克有射程 r 的限制。为方便计算，射程 r 规定为：若坦克位于 (x,y) 格，则它可攻击的目标 (x1,y1) 必须满足 |x-x1|,|y-y1| ∈ [0,r] 。

• 对坦克完成任务的时间有严格限制，规定为 t 秒。其中，坦克每进行一次移动都需 1 秒的时间，每攻击一个目标也需 1 秒的时间。时间一到 t 秒，便对此次任务进行记分。

• 坦克最初位于左上角，且移动方向只准是向右或向下，每次只允许移动一格。

在以上的限制条件下，要完成该任务便成为了一件很难事情。因此，你必须为此编写一个程序，让它助你完成这个艰巨的任务。

【输入格式】

输入文件： gametk.in

第一行右四格整数 N 、 M 、 r 、 t ，分别表示区域的长、宽，以及射程和完成任务时间。

接下来 N 行是一格 N×M 的矩阵，对应每个位置上目标的价值。 1 ≤ N 、 M ≤ 500 ， 1 ≤ r ≤ 100 ， 1 ≤ t ≤ 2500 。

【输出格式】

输出文件： gametk.out

输出文件仅一个数 max ，即该任务中可得到的最高分数。

【输入样例】

5 5 2 7
0 5 0 0 4
0 0 0 0 2
0 0 0 0 0
0 0 0 0 0
5 0 3 0 11

【输出样例】

21