欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

最大子矩阵(小于等于某值)

程序员文章站 2022-03-24 20:48:09
...

最大子矩阵(小于等于某值)
思路:原来的思路就是枚举右下角点和左上角点,复杂度o(n^4)不太行,那我们我们把每一行的前缀和存下来,枚举两行然后枚举列结尾,二分出他前面最小的前缀和使得它大于等于sum-k,最后别忘记特判一下,如果最左边的l也能满足sum-k,l–。

#include<iostream>
#include<cstring>
#include<map>
#include<string.h>
#include<algorithm>
using namespace std;
typedef long long ll;
const int N=252;
int a[N][N];
int l[N][N];
int h[N];
int n,m,kk;
void debug()
{
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++)
			cout<<l[i][j]<<' ';
		cout<<endl;
	}
}
int main()
{
	cin >> n >> m >> kk;
	for(int i=1;i<=n;i++)
		{
			for(int j=1;j<=m;j++)
		{
			cin>>a[i][j];
			l[i][j] = a[i][j] + l[i-1][j];

		}
		//for(int j=1;j<=m;j++)
			//l[i][j]+=l[i][j-1];
	}
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
			l[i][j]+=l[i][j-1];
	//	debug();
	// 0 1 3 5
	int res=0;
	for(int i=1;i<=n;i++)
		for(int j=i;j<=n;j++)
			{
				int sum=0;
				for(int k=1;k<=m;k++)
				{
					h[k] = l[j][k]-l[i-1][k];
					int ll = 0 , rr= k;
					while(ll<rr)
					{
						int mid=ll+rr+1>>1;
						if(h[k]-h[mid]>kk)	ll=mid;
						else	rr = mid-1;
					}
					// 3 4 5
						//h[k]-h[ll+1]<=kk  ll+2 ll+3 
					if(h[k]-h[ll]<=kk)
						ll--;
					res=max(res,(j-i+1)*(k-ll-1));
					//cout<<"i= "<<i<<" j= "<<j<<"  k= "<<k<<" ll= "<<ll<<"	h[k]= "<<h[k]<<" h[l]= "<<h[ll+1]<<' '<<res<<endl;
				}
			}	
			if(!res)	res=-1;
			cout<<res<<endl;
			return 0;		
}
相关标签: 最大子矩阵