ZJU/ZOJ 1636 Evaluate Matrix Sum 解题报告

题目大意是给出一个矩阵，求出矩阵中某些指定子矩阵的所有元素的平方和。

先利用递推预处理出所有以(1,1)为左上角的矩阵的所有元素的平方和。用f[i,j]表示左上角为(1,1)，右下角为(i,j)的矩阵的所有元素的平方和，则f[i,j]=f[i-1,j]+sum[j];sum[j]表示第i行前j个元素的平方和。则所求子矩阵(r1,c1,r2,c2)的所有元素平方和即为f[r2,c2]-f[r1-1,c2]-f[r2,c1-1]+f[r1-1,c1-1]。

1653473    2008-10-01 23:50:40     Accepted    1636    FPC    140    1092    IwfWcf