最大收益问题

た入场券 2022-08-14 05:50 199阅读 0赞

## 最大收益问题 ##

####  ####

##### Time Limit: 2000ms Memory limit: 65536K 有疑问？点这里^\_^ #####

## 题目描述 ##

铁牌狗最近迷上了一款游戏，但铁牌狗实在是太笨了，他还是要请求你的帮助。

有一个n行m列的矩阵A，矩阵A中每个数字均为正整数，现在铁牌狗要在其中选出一个r行c列的子矩阵B，这个子矩阵B中各个数字之和即为铁牌狗的得分，请你帮铁牌狗计算出他的最高得分是多少。

## 输入 ##

首先输入一个组数T(1 <= T <= 10),表示接下来要输入T组数据。

首先输入四个整数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

## 提示 ##

## 来源 ##

zmx

## 示例程序 ##

#include<stdio.h>    
    int a[1001][1001];    
    int main()    
    {    
        int i,j,n,m,k,t,b,c,d,e,l,p1,p2;    
        scanf("%d",&n);    
        for(l=0;l<n;l++)    
        {    
            scanf("%d %d %d %d",&b,&c,&d,&e);    
            for(i=0;i<b;i++)    
                for(j=0;j<c;j++)    
                    scanf("%d",&a[i][j]);    
                t=0;    
                for(i=0;i<=b-d;i++)    
                {    
                    for(j=0;j<=c-e;j++)    
                    {    
                        k=0;    
                        for(p1=i;p1<d+i;p1++)    
                            for(p2=j;p2<e+j;p2++)    
                                k+=a[p1][p2];    
                            if(k>t)    
                                t=k;    
                    }    
                }    
                printf("%d\n",t);    
        }    
    }