题目描述
给定一个 N × M 的矩阵 A,请你统计有多少个子矩阵 (最小 1 × 1,最大 N × 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 × 1 的有 10 个。
大小为 1 × 2 的有 3 个。
大小为 1 × 3 的有 2 个。
大小为 1 × 4 的有 1 个。
大小为 2 × 1 的有 3 个。
对于 30% 的数据,N, M ≤ 20. 对于 70% 的数据,N, M ≤ 100.
对于 100% 的数据,1 ≤ N, M ≤ 50
0; 0 ≤ Ai j ≤ 1000; 1 ≤ K ≤ 250000000.
#include <iostream>
using namespace std;
int a[500][500];
int s[500][500] = { 0 };
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];
s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + a[i][j];
}
}
int cnt = 0;
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= M; j++) {
for (int k = i; k <= N; k++) {
for (int p = j; p <= M; p++) {
if (s[k][p] - s[i - 1][p] - s[k][j - 1] + s[i - 1][j - 1] <= K) {
cnt++;
}
else break;
}
}
}
}
cout << cnt;
return 0;
}
能拿个70%的分,其他的会超时,思路时一遍又一遍遍历这个数组。
最重要的是二维前缀和的公式
s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + a[i][j];
注意a和s都是1下标开头
求出前缀和后我们就可以来求我们的子矩阵和了
文章来源:https://www.toymoban.com/news/detail-402146.html
然后在遍历的同时统计和即可 文章来源地址https://www.toymoban.com/news/detail-402146.html
到了这里,关于蓝桥杯统计子矩阵前缀和C++(附图文超详细讲解)(保姆级)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!