boj 1347 簡單數組問題 在一個二維數組中 a[i][j]=a[i][j]+a[i-1][j]+a[i][j-1]-a[i-1][j-1] 則a[i][j]為i j位置左上側所有元素之和

http://acm.scs.bupt.cn/onlinejudge/showproblem.php?problem_id=1347

1. 在一個二維數組中 a[i][j]=a[i][j]+a[i-1][j]+a[i][j-1]-a[i-1][j-1] 則a[i][j]為i j位置左上側所有元素之和

the position of photo frame Submit: 77    Accepted:27 Time Limit: 2000MS  Memory Limit: 65536K

Description

One day this summer, all the members of BUPT-ACM team take a photo, and we prepare a photo frame, which is used to put photo in it and is a by b. And the wall in 912 is m by n.

However every points of the wall has a number (from 0 to 9) which is means that when the photo frame has cover that point the photo will get an increase of that number.

For example, follow is a 3 by 3 wall, when a 2 by 2 photo frame cover its left-up coner, the phot get a increase of 12 (1+2+4+5 = 12), while when it cover the right-down coner, the photo will get an increase of 28. And the max increase is 28 (5+6+8+9 = 28).

1 2 3

4 5 6

7 8 9

Of course, I want the photo frame has an increase as possible as high. But I can not solve it for this hard problem. So it is the time for you to act for us!

Input

There are many tests, but only one case in each test.

The first line contain two number m, n (1<= m,n <= 1000)

The second line contain two number a, b (1<=a<=m, 1<=b<=n)

Next m lines, each has n numbers from 0 to 9, which means the number of the wall

資料準保合乎出題規範，不用判錯。

Output

Only one number which is the max increase number.

Sample Input

3 3

2 2

1 2 3

4 5 6

7 8 9

Sample Output

28

Hint

Another Sample Input

3 3

2 2

5 0 6

5 5 3

9 2 3

Sample Output

21

#include<iostream>

using namespace std;

int t[1<<10][1<<10];

int main()

{

    int i,j,a,b,n,m,sum=0,k,l,best;

        scanf("%d%d",&m,&n);

         best=0;

         scanf("%d%d",&a,&b);

         for(i=1;i<=m;i++)

          for(j=1;j<=n;j++)

          {

            scanf("%d",&t[i][j]);

            t[i][j] = t[i][j] + t[i - 1][j] + t[i][j- 1] -t[i - 1][j - 1] ;

            }

        for(i=a;i<=m;i++)

           for(j=b;j<=n;j++)

              {

                sum=t[i][j]-t[i-a][j]-t[i][j-b]+t[i-a][j-b];

                if(sum>best)

                    best=sum;          

                              }

           printf("%d/n",best);

           system("pause");

    }