给定一个 N×M 的矩阵 A,请你统计有多少个子矩阵 (最小 1×1,最大 N×M) 满足子矩阵中所有数的和不超过给定的整数 K?
输入格式
第一行包含三个整数 N,M 和 K。
之后 N 行每行包含 M 个整数,代表矩阵 A。
输出格式
一个整数代表答案。
数据范围
对于 30% 的数据,N,M≤20,
对于 70% 的数据,N,M≤100,
对于 100% 的数据,1≤N,M≤500;0≤Aij≤1000;1≤K≤2.5×108。
输入样例:
3 4 10
1 2 3 4
5 6 7 8
9 10 11 12
输出样例:
19
暴力的做法为枚举左上角的下标和右下角的下标 一共四维 O(n ^ 4)
题目给的数据为大于等于0故存在区间单调性 枚举上边界和下边界 缩小成为了一个区间内的子区间和的问题
在一个子区间内 采用双指针算法 右指针右移的时候左指针具有单调性 故可以优化一维变为O(n ^ 3)
固定好上下边界可以预处理 列 的前缀和
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long LL;
const int N = 510;
int n, m, k;
int s[N][N];
int main (){
cin >> n >> m >> k;
for(int i = 1; i <= n; i ++)
for(int j = 1; j <= m; j ++){
scanf("%d", &s[i][j]);
s[i][j] += s[i - 1][j];
}
LL res = 0;
for(int i = 1; i <= n; i ++) // 上边界
for(int j = i; j <= n; j ++){ // 下边界
for(int l = 1, r = 1, sum = 0; r <= m; r ++){
sum += s[j][r] - s[i - 1][r];
while(l <= r && sum > k)
{
sum -= s[j][l] - s[i - 1][l];
l ++;
}
res += r - l + 1;
}
}
cout << res;
return 0;
}