题目链接： http://acm.hdu.edu.cn/showproblem.php?pid=1559
最大子矩阵
Time Limit: 30000/10000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 2901 Accepted Submission(s): 1454
Problem Description
给你一个m×n的整数矩阵，在上面找一个x×y的子矩阵，使子矩阵中所有元素的和最大。
Input
输入数据的第一行为一个正整数T，表示有T组测试数据。每一组测试数据的第一行为四个正整数m,n,x,y（0<m,n<1000 AND 0<x<=m AND 0<y<=n），表示给定的矩形有m行n列。接下来这个矩阵，有m行，每行有n个不大于1000的正整数。
Output
对于每组数据，输出一个整数，表示子矩阵的最大和。
Sample Input
1
4 5 2 2
3 361 649 676
588
992 762 156
992 762 156
993 169
662 34
662 34
638 89 543
525
525
165 254 809 280
Sample Output
2474
Author
lwg
Source
Recommend
/*二维树状数组：同样不要忘记c的初始化，
modify 的功能是改变元素(x, y)，
sum的功能则是求从元素(1, 1)开始到(x, y)的总和，
同样，可以求出任意一个子矩阵内的所有元素之和，
即sum(x2, y2) - sum(x1-1, y2) - sum(x2, y1-1) + sum(x1-1, y1-1)
*/ #include<iostream> using namespace std; int N,M;
int c[][]; int lowbit( int x )
{
return x & (-x);
} void modify( int x, int y, int delta )
{
int i, j;
for(i=x; i<=N; i+=lowbit(i))
{
for(j=y; j<=M; j+=lowbit(j))
{
c[i][j] += delta;
}
}
} int sum( int x, int y )
{
int res = , i, j;
for(i=x; i>; i-=lowbit(i))
{
for(j=y; j>; j-=lowbit(j))
{
res += c[i][j];
}
}
return res;
} void init ()
{
int i,j;
for(i=;i<=N;i++)
for(j=;j<=M;j++)
c[i][j]=; } int main()
{
int t;
scanf("%d",&t);
while(t--)
{
int x,y,i,j,k,temp;
int max = ;
// memset(c,0,sizeof(c));
// c[1005][1005]= {{0}};
scanf("%d%d%d%d",&N,&M,&x,&y);
init (); for(i=;i<=N;i++)
for(j=;j<=M;j++)
{
scanf("%d",&k);
modify(i,j,k);
}
for(i=;i+x-<=N;i++)
for(j=;j+y-<=M;j++)
{
temp=sum(i+x-,j+y-)-sum(i-,j+y-)-sum(i+x-,j-)+sum(i-,j-); if(temp>max)max= temp ;
}
printf("%d\n",max); }
return ; }