HDU 1559 最大子矩阵 (DP)

题目地址:

pid=1559">HDU 1559

构造二维前缀和矩阵。即矩阵上的点a[i][j]表示左上方的点为(0,0),右下方的点为(i,j)的矩阵的和。然后枚举每一个矩阵的左上方的点。因为矩阵的长和宽是固定的,那么这个矩阵实际上也已经固定了。此时这个矩阵的和用公式:

sum=a[i+x-1][j+y-1]-a[i+x-1][j-1]-a[i-1][j+y-1]+a[i-1][j-1];

取最大值就能够了。

代码例如以下:

#include <iostream>
#include <cstdio>
#include <string>
#include <cstring>
#include <stdlib.h>
#include <math.h>
#include <ctype.h>
#include <queue>
#include <map>
#include <set>
#include <algorithm> using namespace std;
#define LL __int64
LL a[1001][1001];
int main()
{
int t, n, m, i, j, k, x, y;
LL z, max1;
scanf("%d",&t);
while(t--)
{
max1=-1;
scanf("%d%d%d%d",&n,&m,&x,&y);
memset(a,0,sizeof(a));
for(i=1;i<=n;i++)
{
for(j=1;j<=m;j++)
{
scanf("%I64d",&z);
a[i][j]=a[i][j-1]+z;
}
}
for(i=1;i<=n;i++)
{
for(j=1;j<=m;j++)
{
a[i][j]+=a[i-1][j];
}
}
for(i=1;i<=n-x+1;i++)
{
for(j=1;j<=m-y+1;j++)
{
z=a[i+x-1][j+y-1]-a[i+x-1][j-1]-a[i-1][j+y-1]+a[i-1][j-1];
if(max1<z)
max1=z;
}
}
printf("%I64d\n",max1);
}
return 0;
}
上一篇:Js 命名空间注册方法


下一篇:Row_Number()显示行号