给定k,n,和n*n的矩阵，求一个子矩形满足权值和在[k,2k]之间

,

这里用到了极大化矩阵的思想。推荐论文《浅谈用极大化思想解决最大子矩阵问题》Orz

如果有一个元素在[k,2k]之间。直接输出就好。

否则。把所有大于2k的元素作为障碍点。

求每一个最大化矩阵。（用单调队列）

如果这个矩阵权值和大于等于k

那么这个矩阵一定有一个子矩阵满足条件。这个结论可以证明。

假设这个矩阵权值和小于等于2k则直接输出这个矩阵。

否则这个矩阵权值和一定大于2k

假设这个矩阵去掉第一行后权值和大于k，则去掉第一行后的矩阵继续操作。

假设权值和小于等于k则矩阵的第一行权值和一定大于k，所以一个一个去除这一行的元素判断即可。

#include
#include
#include
#include
#include
using namespace std;
const long long N=;
long long n,k,a[N][N],book[N][N],sum[N][N],sum1[N][N],top,stack[N],r[N],l[N];
void work(long long x1,long long y1,long long x2,long long y2){
if(sum1[x2][y2]-sum1[x2][y1-]-sum1[x1-][y2]+sum[x1-][y1-]<=*k){ cout<=k){
x2--;
}
while(sum1[x2][y2]-sum1[x2][y1-]-sum1[x2-][y2]+sum1[x2-][y1-]>*k)y1++;
cout<=k&&a[i][j]<=*k){ cout<*k)book[i][j]=;
if(book[i][j])sum[i][j]=;
else sum[i][j]=sum[i-][j]+;
sum1[i][j]=sum1[i-][j]+sum1[i][j-]-sum1[i-][j-]+a[i][j];
}
for(long long i=;i<=n;i++){ top=; for(long long j=;j<=n;j++){ while(sum[i][j]=;j--){
while(sum[i][j]=k){
work(i-sum[i][j]+,l[j],i,r[j]);
return ;
}
}
}
printf("NIE");
return ;
}