题目描述
给定一个 N\times M 的矩阵 A，请你统计有多少个子矩阵（最小 1\times1，最大 N\times M）满足子矩阵中所有数的和不超过给定的整数 K？

输入格式
第一行包含三个整数 N、M 和 K。
之后 N 行每行包含 M 个整数，代表矩阵 A。

输出格式
一个整数代表答案。

样例输入
3 4 10
1 2 3 4
5 6 7 8
9 10 11 12

样例输出
19

样例说明
满足条件的子矩阵一共有 19 个，包含：
大小为 1\times1 的有 10 个。
大小为 1\times2 的有 3 个。
大小为 1\times3 的有 2 个。
大小为 1\times4 的有 1 个。
大小为 2\times1 的有 3 个。

评测用例规模与约定
对于 30\% 的数据，N,M\le 20。
对于 70\% 的数据，N,M\le 100。
对于 100\% 的数据，1\le N,M\le 500，0\le A_{ij}\le 1000，1\le K\le 250000000。

精炼题目:

给定一个矩阵，知道这个矩阵的行列信息，让你求和能够小于k的子矩阵的数量（子矩阵行列是连续的）

思路:

我要关心的是什么:

我只关心每一个子矩阵的和与k的关系

枚举?

让我们来讨论枚举的可能性，一个N*M的矩阵，它的子矩阵为P*Q(P<=N,Q<=M),一个N行得到矩阵，选连续的上下边界top和bottom(top\le bottom),方案数为C_{N+1}^2 = \dfrac{N(N+1)}{2}

(把行数列在数轴上，求连续区间，就是在N个元素里面找到两个不同的分割线，N行就会有N+1个分割线，用组合的方式就能得到上式)

同理，列选左右边界，有

总的子矩阵数为

把极限数值N=M=500带入

需要进行156亿次计算，肯定会超过1秒钟的时间限制，即枚举不可能成功

那要怎么做?

我只对一维数组的处理比较熟悉，如果说题目是让我求一维数组里面的子区间的和不超过k的话，我或许能通过双指针的方式求得，但是这里是一个二维数组，有没有什么办法能把二维数组转化为一维数组呢，我要求的是矩阵的子矩阵的和，我不关心子矩阵里面的一个个元素，我只关心他们的和，所以说我可以抛弃掉元素因素，只留下和因素，那我可以把一个连续行区间的子矩阵i~j，每一列都相应加起来，不就能得到一个只有每列和的一个一维矩阵了:

图示:

那么我们就可以使用压缩矩阵的方式，把每一个子矩阵都压缩成一个一维矩阵，然后把这个一维矩阵输入到判断函数中来判断是否小于k.

由此引出下面几个问题:

1.怎么求子矩阵

2.怎么压缩子矩阵

3.判断函数怎么写

怎么求子矩阵?

要知道矩阵是有行有列的，那就有上界，下界，左界，右界，我们令上界top为0，下界bottom从top开始，遍历到总行数的位置,比如说top从0开始，那么在top=0的时候，bottom依次遍历0,1,2,3…N,就能获得[0,0],[0,1],[0,2]…[0,n]区间的子矩阵，当内层循坏跑完N之后，top转移到1,并从中获得[1,1],[1,2]…[1,n]区间的子矩阵，但是我们发现，获得的子矩阵并不是完整的，它只有行的区别，而他们列是没有区别的，所以说我们需要先压缩子矩阵，得到行压缩子矩阵之后，再对列进行处理，这里我们放到判断函数中去处理

怎么压缩子矩阵?

压缩子矩阵并不困难，我们先令一个空的数组sum[M],这里数组元素的数量要等于列数量，使其能够放入全部列的求和，当bottom向下移动一单位时，我们就把sum每个对应位置的元素都+=bottom所在行的对应列元素，这样子在bottom向下移动的时候，sum每一个对应列的元素会不断加子矩阵下一行对应列的元素，最后输出的sum数组有且只有一行。

判断函数怎么写?

判断函数是对一维数组的判断，这里我们用到双指针的方法（数组元素全部 ≥ 0，可以使用双指针），定义一个左指针l，一个右指针r,核心规则是右指针在压缩矩阵中不断往前走，左指针也不断往前走，两者都不回头，一开始r=l=0,定义sum为窗口的和，计数器(计一个压缩矩阵中子矩阵和小于k的数)为cnt,这个判断由一个for循环和一个while循环组成，for循环负责控制r的步进，while循环负责判断窗口和是否大于k,一开始r=0,进入for循环,sum+=sum[r]，进入while判断，如果窗口和不大于k，while就不进入此时l=0,计数器cnt=0+1，r再次进入for循环，直到窗口和大于k，进入while循环，让l步进，窗口和减去l步进时各个元素的值，再次判断窗口和是否大于k,不是则退出循环，这里cnt+= r-l+1是因为，当r=5不变时，l步进l=1步使得sum<k,即[1,5]区间和是小于k的，那么显然[2,5],[3,5],[4,5][5,5]都是小于k的，其中包含了5-1+1一共五个合法子区间，所以cnt+=r-l+1. 

经过一系列的操作之后，函数返回cnt的值，每一行的压缩矩阵都进入函数一边，再把结果都加入到num中就能拿到答案.

下面是代码展示:

<code>#include <stdio.h>
long long int matrix[500][500];
long long int check(long long sum[], long long int k, long long int m)
{
    long long cnt = 0;
    long long s = 0;
    int l = 0;
    for(int r = 0; r < m; r++)
    {
        s += sum[r];
        while(s > k)
        {
            s -= sum[l];
            l++;
        }
        cnt += r - l + 1;
    }
    return cnt;
}

int main(void)
{
	long long int n,m,k,num=0;
	scanf("%lld %lld %lld",&n,&m,&k);
	
	int top,bottom;//上界与下界
	int x,y;
	for(x=0;x<n;x++)
	{
		for(y=0;y<m;y++)
		{
			scanf("%lld",&matrix[x][y]);
		}
	}
	
	for(top=0;top<n;top++)
	{
		long long int sum[500] = {0};//压缩数组
		int temp;
		for(bottom = top;bottom<n;bottom++)
		{
			for(temp=0;temp<m;temp++)
			{
				sum[temp]+=matrix[bottom][temp];
			}
			num+=check(sum,k,m);
		}
		
	} 
	printf("%lld",num);
	return 0;
	 
}</code>