1559.txt

来自「杭电acm解题报告2001---2099.」· 文本 代码 · 共 48 行

#include <stdio.h>
#include <memory.h>
#define Max 1100
int num[Max][Max];
int dp[Max][Max],dp2[Max][Max];

int main()
{
    int i,j,a,b,n,t,k,m,x,y,mmax;
    scanf("%d",&t);
    {
        while(t--)
        {
            memset(dp,0,sizeof(dp));
            memset(dp2,0,sizeof(dp2));
            scanf("%d%d%d%d",&m,&n,&x,&y);
            mmax=0;
            for(i=0;i<m;i++)
                for(j=0;j<n;j++)
                    scanf("%d",&num[i][j]);
            for(i=0;i<m;i++)
                for(j=0;j<y;j++)
                {
                    dp[i][0]+=num[i][j];
                }
            for(i=0;i<m;i++)
                for(j=1;j<n-y+1;j++)
                {
                    dp[i][j] = dp[i][j-1] + num[i][j+y-1] - num[i][j-1];
                }
            
            for(i=0;i<n;i++)
                for(j=0;j<x;j++)
                {
                    dp2[0][i]+=dp[j][i];
                    mmax = mmax < dp2[0][i] ? dp2[0][i] : mmax;
                }
            for(i=0;i<n;i++)
                for(j=1;j<m-x+1;j++)
                {
                    dp2[j][i] = dp2[j-1][i] + dp[j+x-1][i] - dp[j-1][i];
                    mmax = mmax < dp2[j][i] ? dp2[j][i] : mmax;
                }
            printf("%d\n",mmax);
        }
        return 0;
    }
}