题目链接：http://www.lydsy.com/JudgeOnline/problem.php?id=1047
把一个点右面n个的信息全都保存到这个点上，再把下面n个点的信息全都保存到这个点上，这样就将一个n*n的正方形的全部信息全都保存到了左上角
用倍增统计会快点
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 |
#include<bits/stdc++.h> #define MAXN 1010 using namespace std; inline int rd(){ int x=0,y=1;char c=getchar(); while(c<'0' || c>'9'){if(c=='-')y=-y;c=getchar();} while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar(); return x*y; } int a[MAXN][MAXN],b[MAXN][MAXN]; int n,m,k,ans; void up(int &x,int &y){ if(x<y)x=y; } void down(int &x,int &y){ if(x>y)x=y; } int main(){ n=rd(),m=rd(),k=rd(); for(int i=1; i<=n; i++){ for(int j=1; j<=m; j++){ b[i][j]=a[i][j]=rd(); } } int l=1,s; while(l<k){ for(int i=1; i<=n; i++){ for(int j=1; j<=m; j++){ s=j+l; s=min(s,m-l+1); s=min(s,j+k-l); a[i][j]=max(a[i][j],a[i][s]); b[i][j]=min(b[i][j],b[i][s]); } } l*=2; } l=1; while(l<k){ for(int i=1; i<=n; i++){ for(int j=1; j<=m; j++){ s=i+l; s=min(s,n-l+1); s=min(s,i+k-l); a[i][j]=max(a[i][j],a[s][j]); b[i][j]=min(b[i][j],b[s][j]); } } l*=2; } ans=1000000000; for(int i=1; i<=n-k+1; i++){ for(int j=1; j<=m-k+1; j++){ ans=min(ans,a[i][j]-b[i][j]); } } printf("%d\n",ans); return 0; } |
