最大子矩阵(小于等于某值)
程序员文章站
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;
}
推荐阅读