1.朴素: 暴力枚举每个矩阵
#include<iostream>
using namespace std;
typedef long long LL;
const int N=510;
int n,m,k;
int a[N][N],s[N][N];
int main()
{
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][j-1]+s[i-1][j]-s[i-1][j-1]+a[i][j];
}
LL cnt=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++)
{
int t=s[x2][y2]-s[x1-1][y2]-s[x2][y1-1]+s[x1-1][y1-1];
if(t<=k) cnt++;
}
}
cout<<cnt<<'\n';
return 0;
}
2.优化:
枚举上下边界,然后将上下边界内的 “每列元素” 看成一个元素,
这样就可以把时间复杂度从O(n^4)降到O(n^3)了。
然后枚举由上下边界所确定的区间内的所有右端点,再通过双指针算法,
快速确定合法子区间数量。
#include<iostream>
using namespace std;
typedef long long LL;
const int N=510;
int n,m,k;
int 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<<'\n';
return 0;
}