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

作者: wjyyy 分类: DP,单调队列/单调栈,解题报告 发布时间: 2018-08-27 10:58

点击量:22

 

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

 

题目描述

有一个\(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\)的范围的话,也就是宽度\(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;
}

说点什么

avatar
  Subscribe  
提醒
/* */