题目描述
blablabla
样例
blablabla
算法1
(暴力枚举+二维前缀和) $O(n^4)$
blablabla
时间复杂度
参考文献
C++ 代码
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cmath>
#define INF 0x3f3f3f3f
using namespace std;
typedef long long ll;
int n,m,k;
int a[510][510];
int s[510][510];
int main()
{
cin>>n>>m>>k;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
cin>>a[i][j];
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
{
s[i][j]=s[i-1][j]+s[i][j-1]-s[i-1][j-1]+a[i][j];
}
ll ans=0;
for(int x2=1;x2<=n;x2++)
{
for(int y2=1;y2<=m;y2++)
{
for(int x1=1;x1<=x2;x1++)
{
for(int y1=1;y1<=y2;y1++)
{
if(s[x2][y2]-s[x2][y1-1]-s[x1-1][y2]+s[x1-1][y1-1]<=k) ans++;
}
}
}
}
cout<<ans;
return 0;
}
算法2
(双指针) $O(n^3)$
时间复杂度
参考文献
C++ 代码
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cmath>
#define INF 0x3f3f3f3f
using namespace std;
typedef long long ll;
int n,m,q;
int s[510][510];
int main()
{
cin>>n>>m>>q;
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];
}
ll ans=0;
for(int j=1;j<=m;j++)//枚举子矩阵的右边
for(int i=1;i<=j;i++)//枚举子矩阵的左边
for(int k=1,l=1;k<=n;k++)//k枚举子矩阵的下边,l枚举子矩阵的上边
{
while(l<=k&&s[k][j]-s[k][i-1]-s[l-1][j]+s[l-1][i-1]>q) l++;
if(l<=k) ans+=k-l+1;
}
cout<<ans;
return 0;
}