题目地址：洛谷：【P2219】[HAOI2007]修筑绿化带 – 洛谷

题目描述

为了增添公园的景致，现在需要在公园中修筑一个花坛，同时在画坛四周修建一片绿化带，让花坛被绿化带围起来。
如果把公园看成一个M*N的矩形，那么花坛可以看成一个C*D的矩形，绿化带和花坛一起可以看成一个A*B的矩形。
如果将花园中的每一块土地的“肥沃度”定义为该块土地上每一个小块肥沃度之和，那么，
绿化带的肥沃度=A*B块的肥沃度-C*D块的肥沃度
为了使得绿化带的生长得旺盛，我们希望绿化带的肥沃度最大。

题意简述

给一个M*N矩阵，要求找到一个大小为A*B的子矩阵和这个子矩阵内部一个大小为A*B的子矩阵（该子矩阵不得与外部矩阵边界有交集）使得矩阵和之差最大。

输入输出格式

输入格式：
第一行有6个正整数M,N,A,B,C,D
接下来一个M*N的数字矩阵，其中矩阵的第i行j列元素为一个整数Xij,表示该花园的第i行第j列的土地“肥沃度”。

输出格式：
一个正整数，表示绿化带的最大肥沃程度。

输入输出样例

输入样例#1：

4 5 4 4 2 2
20 19 18 17 16
15 14 13 12 11
10 9 8 7 6
5 4 3 2 1

输出样例#1：

132

说明

数据范围
30%的数据，1<=M,N<=50
100%的数据，1<=M,N<=1000,1<=A<=M,1<=B<=N,1<=C<=A-2,1<=D<=B-2，1<=“肥沃度”<=100

题解

参考资料：[HAOI2007] 修筑绿化带 – CSDN博客
我们可以先处理出每一个宽度为C的行中，每一个右端点i对应的区间[i-B+1, i]中的最小C*D矩阵。这个处理极值显然可以用单调队列实现O(n^2)的处理。
接下来的思路，就是利用我们上面准备好的这个信息来求答案，我们枚举每一列，利用单调队列和上面预处理的信息，我们可以计算出以枚举到的当前行以上不超过A行的C*D矩阵的最小值。也就是说，我们现在正在竖着枚举A*B矩阵，并用单调队列来取出矩阵内的C*D子矩阵的最小值，最后算一波差值更新答案即可。这里的复杂度也是O(n^2)，因此整体复杂度O(n^2)。
比较麻烦的单调队列套路题。

代码

// Code by KSkun, 2018/5
#include <cstdio>
#include <cctype>
#include <cstring>

#include <algorithm>

typedef long long LL;

inline char fgc() {
    static char buf[100000], *p1 = buf, *p2 = buf;
    return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2) ? EOF : *p1++;
}

inline LL readint() {
    register LL res = 0, neg = 1;
    register char c = fgc();
    while(!isdigit(c)) {
        if(c == '-') neg = -1;
        c = fgc();
    }
    while(isdigit(c)) {
        res = (res << 1) + (res << 3) + c - '0';
        c = fgc();
    }
    return res * neg;
}

const int MAXN = 1005;

int n, m, a, b, c, d, sum[MAXN][MAXN], mn[MAXN][MAXN];

inline int queryab(int x, int y) {
    return sum[x][y] - sum[x - a][y] - sum[x][y - b] + sum[x - a][y - b];
}

inline int querycd(int x, int y) {
    return sum[x][y] - sum[x - c][y] - sum[x][y - d] + sum[x - c][y - d];
}

int que[MAXN], ql, qr;

int main() {
    n = readint(); m = readint();
    a = readint(); b = readint();
    c = readint(); d = readint();
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= m; j++) {
            sum[i][j] = readint() + sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1];
        }
    }
    memset(mn, 0x3f, sizeof(mn));
    for(int i = c; i <= n; i++) {
        ql = qr = 0;
        for(int j = d; j <= m; j++) {
            while(ql < qr && que[ql] - d + 1 <= j - b + 1) ql++;
            if(ql < qr) {
                mn[i][j] = querycd(i, que[ql]);
            }
            while(ql < qr && querycd(i, que[qr - 1]) >= querycd(i, j)) qr--;
            que[qr++] = j;
        }
    }
    int ans = 0;
    for(int i = d; i <= m; i++) {
        ql = qr = 0;
        for(int j = c; j <= n; j++) {
            while(ql < qr && que[ql] - c + 1 <= j - a + 1) ql++;
            if(ql < qr && j >= a && i >= b) {
                ans = std::max(ans, queryab(j, i) - mn[que[ql]][i]);
            }
            while(ql < qr && mn[que[qr - 1]][i] >= mn[j][i]) qr--;
            que[qr++] = j;
        }
    }
    printf("%d", ans);
    return 0;
}