洛谷 P2216 [HAOI2007]理想的正方形 题解

一、题目:

洛谷模板

二、思路:

二维ST表.

一般二维的ST表是(f[i][j][k][l])，表示横坐标为(i),往后(2^k)个,纵坐标为(j),往后(2^l)次方个,这样的一个矩形的最大值.

然后看这道题,咦,空间炸了.

再一看,正方形!那还要第四维干什么,k和l永远一样啊!

类似一维ST表,转移即可.

三、代码:

/*
 * @Author: 岸芷汀兰
 * @Date: 2018-10-29 22:42:51
 * @LastEditors: 岸芷汀兰
 * @LastEditTime: 2018-10-29 22:55:49
 * @Description: P2216 of luogu
 */
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>

using namespace std;
template<class Type>
inline Type read(void){
    Type x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return f*x;
}

const int maxn=1005;

int n,m,l,map[maxn][maxn],Log[maxn];

int f[maxn][maxn][15],g[maxn][maxn][15],ans=0x3f3f3f3f;

inline void init(void){
    Log[0]=-1;
    for(register int i=1;i<=1000;++i)Log[i]=Log[i>>1]+1;
    for(register int i=1;i<=n;++i)for(register int j=1;j<=m;++j)f[i][j][0]=g[i][j][0]=map[i][j];
    for(register int k=1;k<=11;++k){
        for(register int i=1;i<=n-(1<<k)+1;++i){
            for(register int j=1;j<=m-(1<<k)+1;++j){
                f[i][j][k]=max(max(f[i][j][k-1],f[i+(1<<(k-1))][j][k-1]),max(f[i][j+(1<<(k-1))][k-1],f[i+(1<<(k-1))][j+(1<<(k-1))][k-1]));
                g[i][j][k]=min(min(g[i][j][k-1],g[i+(1<<(k-1))][j][k-1]),min(g[i][j+(1<<(k-1))][k-1],g[i+(1<<(k-1))][j+(1<<(k-1))][k-1]));
            }
        }
    }
}

inline int calc(int x,int y){
    int tmp1=max(max(f[x][y][Log[l]],f[x][y+l-(1<<Log[l])][Log[l]]),max(f[x+l-(1<<Log[l])][y][Log[l]],f[x+l-(1<<Log[l])][y+l-(1<<Log[l])][Log[l]]));
    int tmp2=min(min(g[x][y][Log[l]],g[x][y+l-(1<<Log[l])][Log[l]]),min(g[x+l-(1<<Log[l])][y][Log[l]],g[x+l-(1<<Log[l])][y+l-(1<<Log[l])][Log[l]]));
    return tmp1-tmp2;
}

int main(){
    n=read<int>();m=read<int>();l=read<int>();
    for(register int i=1;i<=n;++i)
        for(register int j=1;j<=m;++j)
            map[i][j]=read<int>();
    init();
    for(register int i=1;i<=n-l+1;++i){
        for(register int j=1;j<=(m-l+1);++j){
            ans=min(ans,calc(i,j));
        }
    }
    cout<<ans<<endl;
    return 0;
}