本题的暴力算法就要用到n的4次方,要作用话 。
本题的优化是通过计算一维的前缀和来进优化,并用到双指针。首先遍历上下区间,然后通过双指针遍历左右区间,每次遍历都要将右边界的前缀和加到总和上,然后判断总和是否是大于k的如果大于就将左边界向右移,直到满足要求即可。
#include <iostream>
using namespace std;
const int N = 510;
typedef long long LL;
int n,m,K;
int a[N][N];
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin>>n>>m>>K;
for(int i = 1 ;i <= n;i++){
for(int j = 1;j <= m;j++) {
cin>>a[i][j];
a[i][j] += a[i-1][j];
}
}
LL res = 0;
// i和j是用来循环上下边界的
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 += a[j][r] - a[i-1][r];
while(sum > K){
sum -= a[j][l] - a[i-1][l];
l++;
}
// 第二遍写发现的问题 解决了
// 结果是r - l + 1 的原因是:以l这条边界为子矩阵的数量有r-l+1种
// 我们会找出所有满足这种条件的l左边界
res += r - l + 1;
}
}
}
cout<<res<<endl;
return 0;
}