返回题解分享
讨论 / 题解分享/ 帖子详情

统计子矩阵(编程题) - 题解

#include <iostream>
using namespace std;
const int MAXN = 501;

int n, m, k, p[MAXN][MAXN];
long long ans;

inline void scan() {
cin >> n >> m >> k;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
cin >> p[i][j];
p[i][j] += p[i - 1][j] + p[i][j - 1] - p[i - 1][j - 1];
}
}
}

inline int getSum(int i, int j, int u, int v) {
return p[u][v] - p[u][j - 1] - p[i - 1][v] + p[i - 1][j - 1];
}

int main() {
scan();

for (int i = 1; i <= n; i++) {
    for (int j = i; j <= n; j++) {
        for (int col_l = 1, col_r = 1; col_r <= m; col_r++) {
            while (col_l <= col_r && getSum(i, col_l, j, col_r) > k)
            col_l++;
            if (col_l <= col_r) ans += col_r - col_l + 1;
        }
    }
}

cout << ans;
return 0;


}
0 回复 0 转发 0 喜欢 2 阅读
回复 (0)
默认 最新
暂无回复,快来抢沙发!