acwing 4405.统计子矩阵的和

原题链接

解题思路

通过i和j来控制子矩阵的左右边界，通过s和t来控制子矩阵的上下边界，
在子矩阵的和小于k时候，统计子矩阵的个数。

代码

#include<iostream>
using namespace std;

const int N = 550;

int a[N][N];
// i 与 j 控制左右边界， s t控制上下边界 计算二维矩阵和
int main(){
    int n, m,k;
    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][j] + a[i - 1][j] + a[i][j - 1] - a[i - 1][j - 1];//二维前缀和公式
        }
    long long ans = 0;
    for(int i = 1; i <= m; i++){
        for(int j = i; j <= m; j++){
            for(int s = 1, t = 1; t <= n; t++){
                while(s <= t && a[t][j] - a[s - 1][j] - a[t][i - 1] + a[s - 1][i - 1] > k) s++;//只要大于k就令上边界向下逼近
                if(s <= t) ans += t - s + 1;//小于k的时候，加上子矩阵的个数
            }
        }
    }
    cout << ans;
    return 0;
}