那来练手的板子题。
去年普及组考虑单调队列，感觉很慌。
然后打算再复习一波。
就找到了这个题。
题目中(a,b)不大，可以容忍(O(ab))的复杂度。
而且子矩阵的宽度也是有限制的，最大最小也是可以分别分开计算的。
所以可以先统计(n ast 1)大小的矩阵，然后缩成一个元素，表示这个大小的矩阵的值，储存起来。再在缩完后的跑一边(1ast n)的情况，就统计出(nast n)的矩阵了。
然后使用单调队列
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
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]<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
",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);
}