题解 P2219 【[HAOI2007]修筑绿化带】

· · 题解

说看代码理解的你们够了

相信泥萌都是从试炼场刷过来的吧？所以这道题泥萌一定做过了。回顾一下怎么做的呢？二维的单调队列做法：先就某一维上对原始数据进行处理，在对另一维上对前一维的数据进行处理，就得到了所需要的东西。

回到这题，也是同样的做法，下边是我解题时的思路：

  1. 预处理出以A[i,j]、B[i,j]分别为右下角的花坛(C*D)、大矩形(A*B)的肥沃度和

  2. 按行，利用单调队列求出P[i,j]=以A[i, j-B+1+D→j-1]中的最小值，即以(i, j-B+1+D→j-1)为右下角的花坛肥沃度的最小值。

  3. 按列，利用单调队列求出Q[i,j]=以P[i-A+1+C→i-1, j]中的最小值，即以(i-A+1+C→i-1, j-B+1+D→j-1) 为右下角的花坛肥沃度的最小值，显然，这些花坛包含在了以(i,j)为右下角的大矩形中；

  4. 显然B[i,j]-Q[i,j]即为以(i,j)为右下角的绿化带的最大肥沃值。

时间复杂度 O(nm)。代码实现中n、m与题意是反的。欢迎来hack

#include <bits/stdc++.h>
using namespace std;

const int N=1005;

int n,m,A,B,C,D,hd,tl,q[N];
int s[N][N],a[N][N],b[N][N],P[N][N],Q[N][N];

int main() {
    scanf("%d%d %d%d%d%d",&n,&m,&A,&B,&C,&D);
    for(int i=1; i<=n; ++i) {
        for(int j=1; j<=m; ++j) {
            scanf("%d",&s[i][j]);
            s[i][j]=s[i][j]+s[i-1][j]+s[i][j-1]-s[i-1][j-1];
        }
    }
    for(int i=C+1; i<n; ++i) {
        for(int j=D+1; j<m; ++j) {
            a[i][j]=s[i][j]-s[i-C][j]-s[i][j-D]+s[i-C][j-D];
        }
    }
    for(int i=A; i<=n; ++i) {
        for(int j=B; j<=m; ++j) {
            b[i][j]=s[i][j]-s[i-A][j]-s[i][j-B]+s[i-A][j-B];
        }
    }
    for(int i=C+1; i<n; ++i) {
        hd=1, tl=0;
        for(int j=D+1; j<m; ++j) {
            while(hd<=tl && q[hd]<j-B+2+D) hd++; //*
            while(hd<=tl && a[i][q[tl]]>=a[i][j]) tl--;
            q[++tl]=j;
            if(j>=B-1) P[i][j+1]=a[i][q[hd]];
        }
    }
    for(int j=B; j<=m; ++j) {
        hd=1, tl=0;
        for(int i=C+1; i<n; ++i) {
            while(hd<=tl && q[hd]<i-A+2+C) hd++;
            while(hd<=tl && P[q[tl]][j]>=P[i][j]) tl--;
            q[++tl]=i;
            if(i>=A-1) Q[i+1][j]=P[q[hd]][j];
        }
    }
    int ans=0;
    for(int i=A; i<=n; ++i) {
        for(int j=B; j<=m; ++j) {
            ans=max(ans,b[i][j]-Q[i][j]);
        }
    }
    printf("%d\n",ans);
    return 0;
}

* 原来的区间[j-B+1+D, j-1]是对于j来说的；但此处我们在j的位置时更新j+1，所以范围调整为[j-B+2+D, j]。下同。