最大子矩阵

DP问题——最大子矩阵：
[**比赛日期变化**]鉴于11月10日有期中考试,11月份月赛延后2周进行(11月24日)
最大子矩阵

Time Limit: 30000/10000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 2414 Accepted Submission(s): 1221


Problem Description
给你一个m×n的整数矩阵，在上面找一个x×y的子矩阵，使子矩阵中所有元素的和最大。


Input
输入数据的第一行为一个正整数T，表示有T组测试数据。每一组测试数据的第一行为四个正整数m,n,x,y（0

Output
对于每组数据，输出一个整数，表示子矩阵的最大和。


Sample Input
1
4 5 2 2
3 361 649 676 588
992 762 156 993 169
662 34 638 89 543
525 165 254 809 280


Sample Output
2474


#include
#include

#define max(a,b) a>b?a:b
using namespace std;
const int inf=0xFFFFFFF;
const int maxn = 1111;

int dp[maxn][maxn]; ///dp[i][j]:子矩阵(1,1)-->(i,j)的和

int main(){
int T;
scanf("%d",&T);
while(T--){
int n,m,x,y;
scanf("%d%d%d%d",&m,&n,&x,&y);
int sum=-inf;
for(int i=1;i<=m;++i){
dp[i][0]=0;
int s=0;
for(int j=1,a;j<=n;++j){
scanf("%d",&a);
s+=a;
dp[i][j]=s+dp[i-1][j];
if(i>=x&&j>=y)
sum=max(sum,dp[i][j]+dp[i-x][j-y]-dp[i-x][j]-dp[i][j-y]);
}
}
printf("%d\n",sum);
}
return 0;
}