BZOJ 1127 [POI2008]KUP 最大子矩阵

题意:链接方法:最大子矩阵解析:先考虑1*n的情况，如果有在目标区间内的直接输出。否则找是否存在一个区间即可。然后能否推广呢？可以的。如果元素有在目标区间的值的话，直接输出即可。否则的话我们将大于2*k的点看作坏点。则我们只要扫极大子矩阵再进行验证即可。考虑如何验证总和满足目标区间的极大子矩阵。如果是1*n的情况，因为所有的元素都小于k。所以必定有一个前缀的和是在目标区间内的。所以我们只需要缩y2即可。如果是正常的矩阵的话，上下两行一定存在一行满足和小于k，，干掉这一行后判断矩阵和是否满足目标区间，不满足则递归，满足则输出。代码:using namespace std;typedef long long ll;int k,n;ll sum[N][N];ll a[N][N];int le[N][N];int ri[N][N];int h[N][N];ll getsum(int x1,int y1,int x2,int y2){return sum[x2][y2]-sum[x2][y1-1]-sum[x1-1][y2]+sum[x1-1][y1-1];}void print(int x1,int y1,int x2,int y2){while(getsum(x1,y1,x2,y2)>2*k){if(x1==x2)y2–;else if(getsum(x1+1,y1,x2,y2)>=k)x1++;else x2–;}\n”,y1,x1,y2,x2);exit(0);}int main(){scanf(“%d%d”,&k,&n);for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){scanf(“%lld”,&a[i][j]);if(a[i][j]>=k&&a[i][j]<=2*k){\n”,j,i,j,i);return 0;}sum[i][j]=sum[i][j-1]+sum[i-1][j]-sum[i-1][j-1]+a[i][j];}}for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){if(a[i][j]>2*k)le[i][j]=0;else le[i][j]=le[i][j-1]+1;}for(int j=n;j>=1;j–){if(a[i][j]>2*k)ri[i][j]=0;else ri[i][j]=ri[i][j+1]+1;}}for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){&&i!=1){h[i][j]=h[i-1][j]+1;le[i][j]=min(le[i-1][j],le[i][j]);ri[i][j]=min(ri[i-1][j],ri[i][j]);}}}for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){if(a[i][j]<=2*k){int tmp=getsum(i-h[i][j],j-le[i][j]+1,i,j+ri[i][j]-1);if(tmp>=k)print(i-h[i][j],j-le[i][j]+1,i,j+ri[i][j]-1);}}}puts(“NIE”);}

属于自己的不要放弃，已经失去的留作回忆。