题目描述

给出一个矩阵 求出这个矩阵中有几个子矩阵的和不大于k
暴力枚举四个点会超时 但是根据数据范围 是可以接受n的三次方时间复杂度
所以我们只需要优化掉一层循环即可 我们将子矩阵的前缀和看作列的形式
对于每一列求列的前缀和 然后再枚举时 我们只需要枚举所求矩阵的上端点和下端点
再利用双指针 右端点不断向右移动 sum大于k时 我们左端点再向右移动

C++ 代码

#include<iostream>
using namespace std;

#define endl '\n'

typedef long long LL;
const int N = 510;
int n,m,k;
LL s[N][N];

int main()
{
  cin>>n>>m>>k;

  for(int i = 1;i <= n;i ++)
   for(int j = 1;j <= m;j ++)
   {
     cin>>s[i][j];
     s[i][j] += s[i - 1][j];  //初始化列前缀和
   }

  LL res = 0;
  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 += s[j][r] - s[i - 1][r];
      while(sum > k)
      {
        sum -= s[j][l] - s[i - 1][l];
        l ++;
      }
      res += r - l + 1;
    }
    cout<<res;
}

算法2

(暴力枚举)

能过6个测试数据 时间复杂度是n的4次方

C++ 代码

for(int i = 1;i <= n;i ++)
   for(int j = 1;j <= m;j ++)
   {
     cin>>s[i][j];
     s[i][j] += s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1];
   }
  //i,j就是x1,y1, w + i,h + j就是x2,y2
  int res = 0;
  for(int x1 = 1;x1 <= n;x1 ++)
   for(int y1 = 1;y1 <= m;y1 ++)
    for(int x2 = x1;x2 <= n;x2 ++)
     for(int y2 = y1;y2 <= m;y2 ++)
     {
       if(s[x2][y2] - s[x2][y1 - 1] - s[x1 - 1][y2] + s[x1 - 1][y1 - 1] <= k) res ++;
     }
     cout<<res;