山東理工大学第7回ACM校試合-最大収益問題

最大収益問題Time Limit:2000 ms Memory limit:65536 Kに疑問がありますか?ここをクリック^^;タイトルの説明
鉄牌犬は最近ゲームに夢中になっているが、鉄牌犬は本当に愚かで、彼はやはりあなたの助けを求めなければならない.
n行m列のマトリクスAがあります.マトリクスAの各数字は正の整数です.今、鉄牌犬はr行c列のサブマトリクスBを選択します.このサブマトリクスBの各数字の和は鉄牌犬の得点です.鉄牌犬の最高得点はいくらですか.入力
まず1つのグループ数T(1<=T<=10)を入力し、次にTグループデータを入力することを示す.
まず4つの整数n,m,r,c(1<=n,m<=1000,1<=r<=n,1<=c<=m)を入力する.
次のn行は、各行m個の数で、Aの各数字を表す.
マトリクスAの各数字Xは、1<=X<=1000を満たす.出力は、データのセットごとに、答えを表す整数を出力します.サンプル入力
2 4 4 4 4 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 4 4 2 2 1 2 3 3 1 2 3 4 3 3 3 4 1 1 5 5
サンプル出力
40 17

#include <stdio.h>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <cmath>
#include <queue>
#include <stack>
#include <algorithm>
#define INF 0x3f3f3f3f
#define Pi 3.141592654
using namespace std;
const int Max=101000;
int a[1100][1100];
int main()
{
    int T;
    int n,m,r,c;
    int sum;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d %d %d %d",&n,&m,&r,&c);
        for(int i=0;i<n;i++)
        {
            for(int j=0;j<m;j++)
            {
                scanf("%d",&a[i][j]);
            }
        }
        sum=0;
        for(int i=0;i<=n-r;i++)
        {
            for(int j=0;j<=m-c;j++)
            {
                int ans=0;
                for(int k=i;k<i+r;k++)
                {
                    for(int kk=j;kk<j+c;kk++)
                    {
                        ans+=a[k][kk];
                    }
                }
                if(sum<ans)
                {
                    sum=ans;
                }
            }
        }
        cout<<sum<<endl;
    }
    return 0;
}