title: 4405. 统计子矩阵
tags:

• Acwing
• 每日一题
• 前缀和
  categories:
• [ACM]
• [2022大三暑假]
• [C++]
  toc: true
  quicklink: true
  math: true
  sidebar: true
  copyright: true
  reward: true
  date: 2022-08-23 09:16:22

{% note info %}
摘要
Title: 4405. 统计子矩阵
Tag: 前缀和
Memory Limit: 64 MB
Time Limit: 1000 ms
{% endnote %}

Powered by:NEFU AB-IN

Link

4405. 统计子矩阵

• 题意

  给定一个 N×M 的矩阵 A，请你统计有多少个子矩阵 (最小 1×1，最大 N×M) 满足子矩阵中所有数的和不超过给定的整数 K?

• 思路

  利用前缀和+双指针，将其优化为$O(n^3)$

• 代码

  /*
  * @Author: NEFU AB-IN
  * @Date: 2022-08-23 09:44:37
  * @FilePath: \Acwing\4405\4405.cpp
  * @LastEditTime: 2022-08-23 09:56:20
  */
  #include <bits/stdc++.h>
  using namespace std;
  #define N n + 100
  #define SZ(X) ((int)(X).size())
  #define IOS                                                                                                            \
      ios::sync_with_stdio(false);                                                                                       \
      cin.tie(nullptr);                                                                                                  \
      cout.tie(nullptr)
  #define DEBUG(X) cout << #X << ": " << X << '\n'
  typedef pair<int, int> PII;
  
  int a[510][510];
  signed main()
  {
      int n, m, k;
      scanf("%d%d%d", &n, &m, &k);
      for (int i = 1; i <= n; ++i)
      {
          for (int j = 1; j <= m; ++j)
          {
              scanf("%d", &a[i][j]);
              a[i][j] += a[i - 1][j];
          }
      }
      long long res = 0;
      // 枚举上下边界
      for (int i = 1; i <= n; ++i)
      {
          for (int j = i; j <= n; ++j)
          {
              int l = 1, r = 1, sum = 0;
              while (l <= m && r <= m)
              {
                  sum += a[j][r] - a[i - 1][r];
                  while (sum > k)
                  {
                      sum -= a[j][l] - a[i - 1][l];
                      ++l;
                  }
                  res += r - l + 1; // 左边界可以从l取到r
                  ++r;
              }
          }
      }
      printf("%lld\n", res);
      return 0;
  }