【DP】【单调队列】洛谷 P2216 [HAOI2007]理想的正方形题解

算是单调队列的复习吧，不是很难

题目描述

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

输入输出格式

输入格式：

第一行为$3$个整数，分别表示$a,b,n$的值。

第二行至第$a+1$行每行为$b$个非负整数，表示矩阵中相应位置上的数。每行相邻两数之间用一空格分隔。

输出格式：

仅一个整数，为$a\times b$矩阵中所有“$n\times n$正方形区域中的最大整数和最小整数的差值”的最小值。

输入输出样例
输入样例#1：
5 4 2

1 2 5 6

0 17 16 0

16 17 2 1

2 10 2 1

1 2 2 2
输出样例#1：
1
说明

问题规模

(1)矩阵中的所有数都不超过$1,000,000,000$

(2)$20\%$的数据$2\le a,b\le 100,n\le a,n\le b,n\le 10$

(3)$100\%$的数据$2\le a,b\le 1000,n\le a,n\le b,n\le 100$

题解：

乍一看好像是类似前缀和二维容斥，可以$O(n^3)$搞。就是维护每个点向左上角一个边长为$k$的正方形中，最大值和最小值。发现只需要通过$k-1$递推，不用容斥

不过这样的时空都是$O(n^3)$的，数据范围是$1,000$，因此考虑优化。

事实上对于每个点只框定了这$n\times n$的范围的话，也就是宽度$latex n$是一定的，可以想到单队入门题滑动的窗口。不过这里前面每格都还维护了上面$n$个，那么我们就可以先预处理出每个点从自己开始上面$n$个中最大和最小值，这个可以用普通单队处理出来。要注意的是得维护两个单队，一个最小一个最大。

最后只统计右下角$(a-n+1)(b-n+1)$区域的答案，因为只有以这些点为右下角才能凑出完整的$n\times n$正方形来。（剩下部分虽然做了贡献但是不能被统计到答案……伤心:(）

Code：

#include<cstdio>

#include<cstring>

int q1[1010],l1=0,r1=0;//最大

int q2[1010],l2=0,r2=0;//最小

int a[1010][1010];//向上n个最大

int b[1010][1010];//向上n个最小

int c[1010][1010];//原来的矩阵

int main()

{

    memset(b,0x3f,sizeof(b));//注意这里b要取最小值所以要赋初值

    int n,m,k;

    scanf("%d%d%d",&n,&m,&k);

    for(int i=1;i<=n;++i)

        for(int j=1;j<=m;++j)

            scanf("%d",&c[i][j]);

    for(int i=1;i<=m;++i)

    {

        l1=0,r1=0;

        l2=0,r2=0;

        for(int j=1;j<=n;++j)

        {

            if(l1<r1&&q1[l1+1]<=j-k)//超出范围

                ++l1;

            while(l1<r1&&c[q1[r1]][i]<c[j][i])//保证单调（减

                --r1;

            q1[++r1]=j;

            a[j][i]=a[j][i]>c[q1[l1+1]][i]?a[j][i]:c[q1[l1+1]][i];

            if(l2<r2&&q2[l2+1]<=j-k)

                ++l2;

            while(l2<r2&&c[q2[r2]][i]>c[j][i])//保证单调（增

                --r2;

            q2[++r2]=j;

            b[j][i]=b[j][i]<c[q2[l2+1]][i]?b[j][i]:c[q2[l2+1]][i];

        }

    }

    int ans=0x3fffffff;

    for(int i=k;i<=n;++i)

    {

        l1=0,r1=0;

        l2=0,r2=0;

        for(int j=1;j<=m;++j)

        {

            if(l1<r1&&q1[l1+1]<=j-k)

                ++l1;

            while(l1<r1&&a[i][j]>a[i][q1[r1]])

                --r1;

            q1[++r1]=j;

            if(l2<r2&&q2[l2+1]<=j-k)

                ++l2;

            while(l2<r2&&b[i][j]<b[i][q2[r2]])

                --r2;

            q2[++r2]=j;

            if(j>=k)

                ans=ans<a[i][q1[l1+1]]-b[i][q2[l2+1]]?ans:a[i][q1[l1+1]]-b[i][q2[l2+1]];

        }

    }

    printf("%d\n",ans);

    return 0;

}

巴特西

【DP】【单调队列】洛谷 P2216 [HAOI2007]理想的正方形题解

题目描述

输入输出格式

输入输出样例

说明

题解：

Code：

最新文章

热门文章

巴特西

【DP】【单调队列】洛谷 P2216 [HAOI2007]理想的正方形 题解

题目描述

输入输出格式

输入输出样例

说明

题解：

Code：

最新文章

热门文章

【DP】【单调队列】洛谷 P2216 [HAOI2007]理想的正方形题解