算法1
暴力枚举
时间复杂度 $O(n^4)$
C++ 代码
#include<iostream>
using namespace std;
typedef long long LL;
const int N=510;
int n,m,k;
int s[N][N],a[N][N];
int main()
{
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]);
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 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[x1-1][y2]-s[x2][y1-1]+s[x1-1][y1-1]<=k)
res++;
printf("%d",res);
return 0;
}
算法2
前缀和+双指针
时间复杂度 $O(n^3)$
C++ 代码
#include<iostream>
using namespace std;
typedef long long LL;
const int N=510;
int s[N][N];
int n,m,k;
int main()
{
scanf("%d%d%d",&n,&m,&k);
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
{
scanf("%d",&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++)//r是走在前边的指针
{
sum+=s[j][r]-s[i-1][r];
while(sum>k)
{
sum-=s[j][l]-s[i-1][l];//超出部分剪掉
l++;//l向下移动
}
res+=r-l+1;
}
cout<<res<<endl;
return 0;
}
摸摸哒