[HAOI2007] 修筑绿化带

类型：单调队列

传送门：>Here<

题意：给出一个$M*N$的矩阵，每一个代表这一格土地的肥沃程度。现在要求修建一个$C*D$的矩形花坛，矩形绿化带的面积为$A*B$，要求花坛被包裹在绿化带中，且不能碰到绿化带边缘。问绿化带的最大肥沃程度

解题思路

暴力做法：枚举绿化带，然后选出能使其肥沃程度最大的花坛位置。

很容易发现要使绿化带的肥沃程度最大，也就是让所选的花坛的肥沃程度尽量小。由此，问题转化为了求固定矩形内部规定大小的最小子矩形

为了表达方便，以下称绿化带为矩形$AB$，花坛为矩形$CD$。

为了计算方便，我们可以先预处理出以$(i,j)$为右下角的矩形$AB$和矩形$CD$的肥沃程度。利用前缀和处理即可

显然固定矩形$AB$以后，矩形$CD$的可取范围也被固定了。这个范围是可以计算的。设矩形$AB$的右下角为$(i+1,j+1)$，则矩形$CD$的右下角可取范围是$(i+1-(A-1)+C \rightarrow i, j+1-(B-1)+D \rightarrow j)$。也就是$$(i-A+C+2 \rightarrow i, j-B+D+2 \rightarrow j)$$由于我们已经计算出了以$(i,j)$为右下角的矩形$CD$的肥沃程度，因此我们可以把每一个格子看做是一个矩形$CD$。于是要求以同一个$i$作为右下角横坐标的矩形时，他们就是一个横行里的格子。用一个单调队列就很容易求出

求出范围内每一个横行的最小值以后，对所有这些最小值再竖着用单调队列求一个最小值。即可以得出整个范围内的最小值。问题就解决了

这题的代码实现也很难（本蒟蒻打了2.5h+），由于边界条件如此的坑而且样例又如此的水，不得不自己造了好几组数据一个一个调……关键在于把控清楚每一个数组表示的具体内容，包括要不要$+1或-1$

Code

/*By DennyQi 2018.8.19*/

#include <cstdio>

#include <queue>

#include <cstring>

#include <algorithm>

#define  r  read()

#define  Max(a,b)  (((a)>(b)) ? (a) : (b))

#define  Min(a,b)  (((a)<(b)) ? (a) : (b))

using namespace std;

typedef long long ll;

const int MAXN = ;

const int INF = ;

inline int read(){

    int x = ; int w = ; register int c = getchar();

    while(c ^ '-' && (c < '' || c > '')) c = getchar();

    if(c == '-') w = -, c = getchar();

    while(c >= '' && c <= '') x = (x<<) + (x<<) + c - '', c = getchar();

    return x * w;

}

int M,N,A,B,C,D,h,t;

int a[MAXN][MAXN],sum[MAXN][MAXN],ab[MAXN][MAXN],cd[MAXN][MAXN];

int q[MAXN],mcd[MAXN][MAXN],mx[MAXN][MAXN];

int main(){

    N = r, M = r;

    A = r, B = r, C = r, D = r;

    for(int i = ; i <= N; ++i){

        h = , t = ;

        for(int j = ; j <= M; ++j){

            a[i][j] = r;

            sum[i][j] = sum[i-][j] + sum[i][j-] - sum[i-][j-] + a[i][j];

            ab[i][j] = sum[i][j] - sum[i][j-B] - sum[i-A][j] + sum[i-A][j-B];

            cd[i][j] = sum[i][j] - sum[i][j-D] - sum[i-C][j] + sum[i-C][j-D];

            if(i > C && j > D && i < N && j < M){

                while(h <= t && cd[i][q[t]] >= cd[i][j]) --t;

                q[++t] = j;

                if(j - B + D +  > ){

                    while(h <= t && q[h] < j - B + D + ) ++h;

                }

                if(i > C && j > D) mcd[i][j] = cd[i][q[h]];

            }

        }

    }

    for(int k = B; k <= M; ++k){

        h = , t = ;

        q[] = ;

        for(int i = C+; i <= N; ++i){

            while(h <= t && q[h] < i - A + C + ) ++h;

            if(i >= A) mx[i][k] = mcd[q[h]][k-];

            while(h <= t && mcd[q[t]][k-] >= mcd[i][k-]) --t;

            q[++t] = i;

        }

    }

    int ans = ;

    for(int i = A; i <= N; ++i){

        for(int j = B; j <= M; ++j){

            ans = Max(ans, ab[i][j] - mx[i][j]);

        }

    }

    printf("%d", ans);

    return ;

}

巴特西

[HAOI2007] 修筑绿化带

最新文章

热门文章