赞
踩
和一维前缀和一样 一维前缀和
1)构造一个二维数组s[N][N]使得二维数组里的每一个元素都是原来数组的前缀和
s[i][j] = s[i][j-1]+s[i-1][j]-s[i-1][j-1]+a[i][j];
2)要求子矩阵的和,则可以通过s[N][N]来求
s[x2][y2]-s[x2][y1-1]-s[x1-1][y2]+s[x1-1][y1-1];
#include<stdio.h> #define N 1001 int a[N][N],s[N][N]; int main(void) { int n,m,q,i,j; scanf("%d%d%d",&n,&m,&q); for(i=1; i<=n; i++) { for(j=1; j<=m; j++) { scanf("%d",&a[i][j]); s[i][j] = s[i][j-1]+s[i-1][j]-s[i-1][j-1]+a[i][j]; } } while(q--) { int x1,y1,x2,y2; scanf("%d%d%d%d",&x1,&y1,&x2,&y2); printf("%d\n",s[x2][y2]-s[x2][y1-1]-s[x1-1][y2]+s[x1-1][y1-1]); } }
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。