问题 24780 --【USACO2014MARCH】懒牛{silver题2}

24780: 【USACO2014MARCH】懒牛{silver题2}

时间限制: 2 Sec  内存限制: 256 MB
提交: 7  解决: 5
[提交][状态][讨论版][命题人:]

题目描述

2. 懒牛{silver2}

【问题描述】

奶牛贝西非常懒惰,她希望在她的地盘内找到一点最佳位置居住,以便在有限的步数内可以吃到尽量多的青草。

她的地盘是一个N行N列(1 <= N <= 400)的矩阵,第r行c列包含G(r,c)单位的青草(0 <= G(r,c) <= 1000)。从她的居住点,她最多愿意走K步(0 <= K <= 2*N),每一步她可以找到上、下、左、右直接相邻的某个格子。

例如,她的居住地在B处:

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时,她只愿意到标有*的位置。

请帮助她确定一个最佳的居住点,使她能吃到的最多的草。

【文件输入】

第一行,两个用空格隔开在整数N和K。

接下来N行N列的矩阵,每个数字表示草的数量。

【文件输出】

一个整数,表示她能吃到的最多的草量。

【输入样例1】

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

【输出样例1】

342

提示


Analysis: The Lazy Cow [Silver] by Fatih Gelgi





The straightforward idea is to try brute-force: for each cell (r,c), calculate the amount of grass in K steps. This approach requires O(N^2 K^2) which is slow considering the given bounds in the problem. A simple observation is that we don't need to recalculate the sum of the square region each time. Instead we can slide it by removing the values of former cells and adding values of new cells. The number of cells to remove and add is O(K) as opposed to O(K^2).



Note that the reachable cells from a cell compose a square of size K which is tilted 45 degrees. How to slide that tilted square? While sliding a square is simple, this one seems rather complicated. An idea is to rotate the grid instead of rotating the sliding window as shown in the example below:


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


Now we can slide it easily by subtracting the first column in the region from the sum and adding the next column after the region to the sum. Note that the matrix includes non-lattice points too (i.e. extra zeros in the matrix). Bessie can be positioned in lattice points only; that needs an extra check.



In this approach, the complexity is reduced to O(KN^2). The required memory becomes 4 times more but it is not a trouble since N is small. Although the solution can have further optimization, this one is rather easy to implement and more than sufficient for the problem. A sample code is provided below:


#include <fstream>

#define MAX 801

using namespace std;

int n,k,mat[MAX][MAX],best;

int main()
{
ifstream fin("lazy.in");
fin >> n >> k;
// rotate the matrix 45 degrees
for (int i=0; i<n; i++)
for (int j=0; j<n; j++)
fin >> mat[i+j][n-i+j-1];
fin.close();

// 45 degree rotation expands the size of the matrix
// it also includes the cells with half distance
int t=(n+1)%2; // t is used to avoid non-lattice points
n=n*2-1;
for (int i=0; i<n; i++,t=1-t)
{
// calculate the sum of 2k x 2k region
// Bessie can only be positioned in lattice points
int sum=0;
for (int a=max(i-k,0); a<n && a<=i+k; a++)
for (int b=max(t-k,0); b<n && b<=t+k; b++)
sum+=mat[a][b];
if (best<sum) best=sum;

// slide the region
for (int j=t+1; j+k<n; j++)
{
for (int a=max(i-k,0); a<n && a<=i+k; a++)
{
if (j-k-1>=0) sum-=mat[a][j-k-1];
sum+=mat[a][j+k];
}
// update the sum only in lattice points
if (j%2==t && best<sum) best=sum;
}
}

ofstream fout("lazy.out");
fout << best << endl;
fout.close();
}

来源

 

[提交][状态]