返回题解分享
讨论 / 题解分享/ 帖子详情

统计子矩阵(编程题) - 题解

#include<bits/stdc++.h>

using namespace std;

int n,m,k;

int a[505][505];

long long ans=0;

int main(){

//ios::sync_with_stdio(false),cout.tie(0),cin.tie(0);

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]+a[i][j-1]-a[i-1][j-1];


}


}

for(int i=1;i<=m;++i){

for(int j=i;j<=m;++j){

	for(int p=1,q=1;q<=n;++q)

	{

		while(p<=q&&a[q][j]-a[q][i-1]-a[p-1][j]+a[p-1][i-1]>k){

			p++;

			 //一直让p指针下移到权值和<=k

		}

		if(p<=q){

		 //在当前i,j的情况下,此时p q 之间的所有子矩阵都满足条件,一共q-p+1行

			ans+=(q-p+1);

		}

	}

}


}

cout<<ans;

return 0;


}
0 回复 0 转发 0 喜欢 1 阅读
回复 (0)
默认 最新
暂无回复,快来抢沙发!