内存限制：256 MB 时间限制：1 S 标准输入输出

题目类型：传统 评测方式：文本比较 上传者：外部导入

提交：310 通过：74

题目描述

给定一个 N × M 的矩阵A，请你统计有多少个子矩阵(最小 1 × 1，最大 N × M) 满足： 子矩阵中所有数的和不超过给定的整数K?

输入格式

第一行包含三个整数N, M 和K. 之后 N 行每行包含 M 个整数，代表矩阵A. 30%的测试数据：1≤N,M≤20； 70%的测试数据：1≤N,M≤100； 100%的测试数据：1≤N,M≤500；0≤Aij≤1000；1≤K≤250000000。

输出格式

一个整数代表答案。

输入样例 复制

输出样例 复制

数据范围与提示

满足条件的子矩阵一共有19，包含： 大小为1 × 1 的有10 个。 大小为1 × 2 的有3 个。 大小为1 × 3 的有2 个。 大小为1 × 4 的有1 个。 大小为2 × 1 的有3 个。

可笑的是，第一次看到这个题，写了一个六层循环，吓死人！

对于这种二维矩阵，求和，可以用dp[i][j]来表示matr[0][0]到matr[i][j]的和,    这样能简便后面求和的步骤，减少两阶的时间复杂度，这是二维前缀和。

   同时，一维前缀和怎么表示呢?dp[i][j]表示matr[0][j]到matr[i][j]的和，这只表示    第j列前面i行的和。所以这就是一维前缀和和二位前缀和的区别

对于递增的二维前缀和，如果要计算子矩阵个数等问题，可以先固定行号，再迭代列号进行遍历，这样可以根据递增的性质减少时间复杂度，实现三重循环。因为如果先固定左上角坐标，再固定右下角坐标，则会出现四重循环，即不能利用二维前缀和递增的性质。