P8391 - The Lazy Cow

内存限制：128 MB 时间限制：1 S 标准输入输出

题目类型：传统评测方式：文本比较上传者：

提交：1 通过：1

It's a hot summer day, and Bessie the cow is feeling quite lazy. She wants to locate herself at a position in her field so that she can reach as much delicious grass as possible within only a short distance. The field Bessie inhabits is described by an N by N grid of square cells (1 <= N <= 400). The cell in row r and column c (1 <= r,c <= N) contains G(r,c) units of grass (0 <= G(r,c) <= 1000). From her initial square in the grid, Bessie is only willing to take up to K steps (0 <= K <= 2*N). Each step she takes moves her to a cell that is directly north, south, east, or west of her current location. For example, suppose the grid is as follows, where (B) describes Bessie's initial position (here, in row 3, column 3): 50 5 25* 6 17 14 3* 2* 7* 21 99* 10* 1*(B) 2* 80* 8 7* 5* 23* 11 10 0 78* 1 9 If K=2, then Bessie can only reach the locations marked with *s. Please help Bessie determine the maximum amount of grass she can reach, if she chooses the best possible initial location in the grid.
这是一个炎热的夏日，奶牛贝西感到很懒。她想要

将自己定位在自己领域的某个位置，这样她就可以达到

在很短的距离内尽可能地种植美味的草。

贝西居住的区域由N×N的方形网格描述

（1<=N<=400）。行r和列c（1<=r，c<=N）中的单元格包含

草的G（r，c）单位（0<=G（r，c）<=1000）。从她最初的方块开始

在网格中，贝西只愿意执行最多K个步骤（0<=K<=2*N）。

她走的每一步都会把她带到一个正北、正南的牢房，

她现在所在位置的东部或西部。

例如，假设网格如下所示，其中（B）描述了贝西的

初始位置（此处第3行第3列）：

50 5 25* 6 17

14 3* 2* 7* 21

99*10*1*（B）2*80*

8 7* 5* 23* 11

10 0 78* 1 9

如果K=2，则贝西只能到达标有*s的位置。

请帮助贝西确定她能够到的最大草量，如果

她在网格中选择可能的最佳初始位置。

* Line 1: The integers N and K. * Lines 2..1+N: Line r+1 contains N integers describing row r of the grid.

* Line 1: The maximum amount of grass Bessie can reach, if she chooses the best possible initial location (the location from which she can reach the most grass).

In the example above, Bessie can reach 342 total units of grass if she locates herself in the middle of the grid.

5 2
50 5 25 6 17
14 3 2 7 21
99 10 1 2 80
8 7 5 23 11
10 0 78 1 9

2014 March Contest Silver

8391: The Lazy Cow

题目描述

输入格式

输出格式

输入样例复制

输出样例复制

分类标签