前缀和(SJTU OJ 1002)

SJTU OJ 1002

Description

二哥在自己的后花园里种了一些花生,也快到了收获的时候了。这片花生地是一个长度为L、宽度为W的矩形,每个单位面积上花生产量都是独立的。他想知道,对于某个指定的区域大小,在这么大的矩形区域内,花生的产量最大会是多少。

Input Format

第1行有2个整数,长度L和宽度W。 第2行至第L+1行,每行有W个整数,分别表示对应的单位面积上的花生产量A( 0< A<10 ) 。 第L+2行有2个整数,分别是指定的区域大小的长度a和宽度b。

Output Format

输出一个整数m,表示在指定大小的区域内,花生最大产量为m。

Sample Input

4 5
1 2 3 4 5
6 7 8 0 0
0 9 2 2 3
3 0 0 0 1
3 3

Sample Output

38

样例解释

左上角:38 = (1+2+3) + (6+7+8) + (0+9+2)

数据范围

对于30%的数据: ( 1 < L,W < 100 );

对于100%的数据: ( 1 < L,W < 1000 );

全部区域大小满足:( 1 < a < L ,1 < b < W ) 。


解法

其实这道题有一点物化技术的思想,因为如果暴力计算的话我们会发现有很多部分是重复计算的,在数据处理当中对于这种重复计算的东西,可以把事先计算好的值保存下来,减少计算的复杂度。

在网上有的人是用'前缀和'这样的概念来描述并解决这个问题的:

我们先考虑一维的情形,如果我事先计算出 pre[i] 表示前1-i个格子内数字之和,那么完成这个处理之后,每次想要得到任意一个区间 [l, r]的数字和,只需要计算 pre[r] - pre[l -1]即可。随即我们可以推广到二维,事先计算pre[i][j]表示以1, 1为左上角,i, j为右下角的矩形内数字之和。那么不难推出如果要取得以x1, y1为左上角 x2, y2为右下角的矩形内数字之和,只需计算 pre[x2][y2] - pre[x1 - 1][y2] - pre[x2][y1 - 1] + pre[x1 - 1][y1 - 1] 即可。

#include<iostream>

using namespace std;

int main()
{
int L(0), W(0), t(0);
cin >> L >> W; //输入花生地的长和宽
//定义数组
int **store = new int*[L];
for (int i = 0; i < L; ++i) store[i] = new int[W];
for (int i = 0; i < L; ++i){
for (int j = 0; j < W; ++j){
cin >> t;
if (j>0&&i>0)store[i][j] = store[i-1][j] + t + store[i][j-1] - store[i-1][j-1];
else if (j>0 && i == 0)store[i][j] = t + store[i][j-1];
else if (i > 0 && j == 0)store[i][j] = t + store[i - 1][j];
else store[i][j] = t;
}
}
int l, w, result(0), temp(0);
cin >> l >> w;//获得目标区块的大小
//遍历计算
for (int i = l - 1; i < L; ++i){
for (int j = w - 1; j < W; ++j){
if(i == l- 1 && j == w - 1)temp = store[i][j];
else if (i == l - 1 && j != w - 1)temp = store[i][j] - store[i][j - w];
else if (i != l - 1 && j == w - 1)temp = store[i][j] - store[i - l][j];
else temp = store[i][j] - store[i - l][j] - store[i][j-w] + store[i-l][j-w];
if (temp >= result)result = temp;
}
}
cout << result;//输出结果
//释放内存!
for (int i = 0; i < L; ++i)
delete[] store[i];
delete[] store;
return 0;
}