那来练手的板子题。

去年普及组考虑单调队列，感觉很慌。

然后打算再复习一波。

就找到了这个题。

题目中\(a,b\)不大，可以容忍\(O(ab)\)的复杂度。

而且子矩阵的宽度也是有限制的，最大最小也是可以分别分开计算的。

所以可以先统计\(n \ast 1\)大小的矩阵，然后缩成一个元素，表示这个大小的矩阵的值，储存起来。再在缩完后的跑一边\(1\ast n\)的情况，就统计出\(n\ast n\)的矩阵了。

然后使用单调队列

#include
    
     #include
     
      #include
      
       #include
       
        using std::min;const int maxn=1010;int base[maxn][maxn];int T[maxn][maxn][2];struct node{    int l,r;    int pos[maxn],val[maxn];    void clear()    {        l=0,r=1;    }    void push(int Val,int Pos)    {        while(val[l]
        
         =r) l--;        l++;        pos[l]=Pos;        val[l]=Val;        return ;    }    void pop(int Pos)    {        while(pos[r]<=Pos&&r<=l)            r++;        return ;    }    int front()    {        return val[r];    }};node Max,Min;int main(){    int A,B,n;    scanf("%d%d%d",&A,&B,&n);    for(int i=1;i<=A;i++)        for(int j=1;j<=B;j++)            scanf("%d",&base[i][j]);    for(int i=1;i<=B;i++)    {        Max.clear();Min.clear();        for(int j=1;j<=n;j++)            Max.push(base[j][i],j),            Min.push(-base[j][i],j);        for(int j=1;j<=A-n+1;j++)        {            T[j][i][0]=Max.front();            T[j][i][1]=Min.front();            Max.pop(j);Min.pop(j);            Max.push(base[j+n][i],j+n);            Min.push(-base[j+n][i],j+n);        }    }    int ans=0x7fffffff;    for(int i=1;i<=A-n+1;i++)    {        Max.clear();Min.clear();        for(int j=1;j<=n;j++)            Max.push(T[i][j][0],j),            Min.push(T[i][j][1],j);        for(int j=1;j<=B-n+1;j++)        {            //printf("%d,%d:%d %d\n",i,j,Max.front(),Min.front()*-1);            ans=min(ans,Max.front()+Min.front());            Max.pop(j),Min.pop(j);            Max.push(T[i][j+n][0],j+n);            Min.push(T[i][j+n][1],j+n);        }    }    printf("%d",ans);}