hev神让我做做这题...
大概我们可以用一个二维的单调队列来写的。
用两个矩阵来记录大矩阵的部分最值。
例如用A[i][j]来记录mat[i][j]---mat[i+r-1][j]这一列的最小值，用Mi[i][j]来记录A[i][j]--A[i][j+c-1]这一行的最小值，于是乎Mi[i][j]就是mat[i,i+r-1][j,j+c-1]这个r*c的子矩阵的最小值了。
我的代码相当挫
大家都是530++ms AC的 我却要970ms.... 再看看别人的代码...
发现压线过特别有快感啊！
#include<iostream>
#include<string>
#include<cstdio>
#define MN 1111
#define INF 0x7F7F7F7F
#define FF(i,N) for( int i=0;i<N;i++ )
using namespace std;int mat[MN][MN];
int A[MN][MN],B[MN][MN],Mi[MN][MN],Ma[MN][MN];
int n,m,r,c;
struct node{int id,v;
}mi[MN],ma[MN];
int hemi,hema;void insert( int num,int y )
{while( y-mi[hemi].id>=r&&mi[hemi].v!=INF ) hemi++;while( y-ma[hema].id>=r&&ma[hema].v!=INF ) hema++;int i;for( i=hemi;mi[i].v!=INF;i++ )if( mi[i].v>num )break;mi[i].v=num;mi[i].id=y;for( i=hema;ma[i].v!=INF;i++ )if( ma[i].v<num )break;ma[i].v=num;ma[i].id=y;
}void insert0( int num,int y )
{while( y-mi[hemi].id>=c&&mi[hemi].v!=INF ) hemi++;if( num==INF ) return;int a=0;for( a=hemi;mi[a].v!=INF;a++ )if( mi[a].v>num )break;mi[a].v=num;mi[a].id=y;
}void insert1( int num,int y )
{while( y-ma[hema].id>=c&&mi[hema].v!=INF ) hema++;if( num==INF ) return;int a=0;for( a=hema;ma[a].v!=INF;a++ )if( ma[a].v<num )break;ma[a].v=num;ma[a].id=y;
}
int main()
{while( scanf("%d%d%d%d",&n,&m,&r,&c)!=EOF ){for( int i=1;i<=n;i++ )for( int j=1;j<=m;j++ )scanf( "%d",&mat[i][j] );for( int j=1;j<=m;j++ ){memset(mi,0x7F,sizeof(mi));memset(ma,0x7F,sizeof(ma));hemi=hema=0;for( int i=1;i<=n;i++ ){insert(mat[i][j],i);if( i>=r ){A[i-r+1][j]=mi[hemi].v;B[i-r+1][j]=ma[hema].v;}}}int ans=0;for( int i=1;i-r+1<n;i++ ){memset(mi,0x7F,sizeof(mi));memset(ma,0x7F,sizeof(ma));hema=hemi=0;for( int j=1;j-c+1<m;j++ ){insert0( A[i][j],j );insert1( B[i][j],j );if( j>=c ){Mi[i][j-c+1]=mi[hemi].v;Ma[i][j-c+1]=ma[hema].v;ans=max( ans,Ma[i][j-c+1]-Mi[i][j-c+1] );}}}printf( "%d\n",ans );}return 0;
}