[HAOI2007] 理想的正方形

题意

有一个 的整数组成的矩阵,现请你从中找出一个 的正方形区域,使得该区域所有数中的最大值和最小值的差最小。

分析

好多人用什么倍增的算法,还有用线段树的。。。

我们考虑一下,要求以 为右下角的 的正方形中的最大值和最小值(以最大值为例)

暴力

暴力,总复杂度 .

暴力 DP

表示 为右下角, 的正方形中的最大值。

复杂度 .

倍增 DP

表示 为右下角, 的正方形中的最大值

复杂度 .

单调队列

没错,这就是我要讲的算法

受到暴力 DP 的启发,我们发现暴力 DP 用了三个边长小 1 的正方形来更新当前的正方形

而这有点浪费,因为三个正方形有重复部分(即 为左上角, 为右下角的部分)

那么如何优化呢。。。其实我们可以用互不重叠的一组矩形在凑出正方形啊

考虑 表示以 为右下角,宽度为 ,高度为 的条状矩形中的最大值

显然对于 ,可以单调队列一起求啊,也就是维护一个从队首到队尾单调递减队列,保证队首下标与当前下标距离不超过 n,然后维护一下

那么有了 ,我们再用 来一次纵向的宽度为 ,高度为 的条状矩形中的最大值不就完了吗

复杂度

最后,本座为了避免写太多代码,求了 之后,横竖交换,再求一次横向的即可

代码

#include<cstdio>
#include<cctype>
#include<algorithm>
#define FOR(i,j,k) for(int i=j;i<=k;i++)
#define swap(x,y) (x^=y^=x^=y)
using namespace std;
const int N=1003;
int a,b,n,ans=0x3f3f3f3f;
int c[N][N],d[N][N],g[N][N],h[N][N],f[N][N];
// 快读
char nc(){static char buf[100000],*p1=buf,*p2=buf;
    return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;
}
int rd(){int res=0;char c=nc();
    while(!isdigit(c))c=nc();
    while(isdigit(c))res=res*10+c-'0',c=nc();
    return res;
}
int calc1(int * v,int * ans){// 单调队列计算 v[i-n+1..i] 的最大值,保存在 ans[i] 中
    int q[N*2][2],l=1,r=0;
    FOR(i,1,b){while(l<=r&&q[r][0]<=v[i])r--;
        while(l<=r&&q[l][1]+n<=i)l++;
        q[++r][0]=v[i],q[r][1]=i;
        ans[i]=q[l][0];
    }
}
int calc2(int * v,int * ans){// 单调队列计算 v[i-n+1..i] 的最小值,保存在 ans[i] 中
    int q[N*2][2],l=1,r=0;
    FOR(i,1,b){while(l<=r&&q[r][0]>=v[i])r--;
        while(l<=r&&q[l][1]+n<=i)l++;
        q[++r][0]=v[i],q[r][1]=i;
        ans[i]=q[l][0];
    }
}
int main(){a=rd(),b=rd(),n=rd();
    FOR(i,1,a)FOR(j,1,b)c[i][j]=rd();// 读入
    FOR(i,1,a)calc1(c[i],d[i]),calc2(c[i],h[i]);// 横向计算最大最小
    FOR(i,1,a)FOR(j,i+1,b)swap(d[i][j],d[j][i]),swap(h[i][j],h[j][i]);// 横竖交换
    swap(a,b);// 横竖交换,之前的横向的最大最小变成了纵向的最大最小
    FOR(i,1,a)calc1(d[i],g[i]),calc2(h[i],f[i]);// 在之前算出的结果上再次横向计算,得到正方形的最大最小
    FOR(i,n,a)FOR(j,n,b)ans=min(ans,g[i][j]-f[i][j]);// 统计答案
    printf("%d",ans);
    return 0;
}

 上一篇
[SCOI2005] 最大子矩阵 [SCOI2005] 最大子矩阵
题意矩形的每一个格子有权值 一个宽 1 或 2 的矩形选出 k 个子矩形,问最大权值和 分析既然宽度只有 2, 状压一下每行状态 DP 即可 定义 表示前 行选 个子矩形的最大权值. 其中 k: k=
2018.12.13
下一篇 
树链剖分 ·Decomposition 树链剖分 ·Decomposition
摘要 树链剖分用于将树分割成若干条链的形式,以维护树上路径的信息。 具体来说,将整棵树剖分为若干条链,使它组合成线性结构,然后用其他的数据结构维护信息。 不同的剖分方案会导致不同的时间复杂度。在这其中极常见的是轻重链剖分(Heavy-Lig
2018.12.07
  目录