「Luogu 2219」「HAOI2007」修筑绿化带 (单调队列+细节)

发表于 | | + s

2219
题意：在$n \times m$的矩阵中找出一块$a \times b$的矩形，在这个矩形中找出一块$c \times d$的矩形(必须在内部)，得分为$a \times b$的矩形分数减去$c \times d$的矩形，求分数最大的$a \times b$的矩形，输出分数。

细节题
这题感觉类似Bzoj 1047，问法类似，并且都是压缩了一段区间然后边成序列问题。
这题可以考虑枚举每个$a \times b$的矩形，然后每次在矩形中找出一块分数最小的$c \times d$的矩形(注意必须在内部)，然后减掉即可。

1、 先预处理$n \times m$的矩阵的二维前缀和
2、 然后预处理每个$((x,y) | x+c \leq m, y+d \leq n)$为左上角的$c \times d$的矩形的分值和记为$S(x,y)$
3、 对于每个$((x,y) | x+c \leq m, y+d \leq n)$，记录
$$
C(x,y)=\min\limits_{1 \leq i \leq a - 2 -c +1}S(x+i-1,y)
$$
这个相当于把这个$a \times b$的矩形的一列决策点都压缩成一个元素
4、对于每行$(x | x+a-1 \leq m)$, 每列$(y|y \geq 2, y+d-1\leq n)$，单调队列记录
$$
\min\limits_{y \in [y-(b - 2 - d + 1 + 1), y]}C(x+1,k)
$$
然后得到了最小值，按上面方法计算即可
( 范围什么的还是自己算算吧，太杂乱了可能上面的公式会有错误

#include<cstdio> 
#include<cstring>
#include<algorithm>
#include<iostream>
#include<vector>
#include<set>
#include<string>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db long double
#define fir first
#define sec second
#define mp make_pair
using namespace std;

namespace flyinthesky {

    const int MAXN = 1000 + 5, INF = 2000000000;

    int m, n, a, b, c, d, orz[MAXN][MAXN], qzh[MAXN][MAXN];
    int S[MAXN][MAXN], C[MAXN][MAXN];
    int q[MAXN], l, r;

    int qry(int u, int v, int x, int y) {return qzh[x][y] - qzh[x][v - 1] - qzh[u - 1][y] + qzh[u - 1][v - 1];}

    int work(int a, int b, int c, int d) {

        ms(S, 0), ms(C, 0);
        int ret = 0;

        for (int i = 1; i + c - 1 <= m; ++i) 
        for (int j = 1; j + d - 1 <= n; ++j) S[i][j] = qry(i, j, i + c - 1, j + d - 1);

        for (int y = 1; y + d - 1 <= n; ++y) {
            l = 1, r = 0;
            for (int x = m - c + 1; x >= 1; --x) {
                while (l <= r && q[l] - x >= a - 2 - c + 1) ++l;
                while (l <= r && S[x][y] <= S[q[r]][y]) --r;
                q[++r] = x;
                C[x][y] = S[q[l]][y];
            }
        }

        for (int x = 1; x + a - 1 <= m; ++x) {
            int tr = x + 1;
            l = 1, r = 0;
            for (int i = 2; i <= b - d; ++i) {
                while (l <= r && C[tr][i] <= C[tr][q[r]]) --r;
                q[++r] = i;
            }
            ret = max(ret, qry(x, 1, x + a - 1, b) - C[tr][q[l]]);
            for (int y = b - d + 1; y + d - 1 <= n; ++y) {
                while (l <= r && y - q[l] >= b - 2 - d + 1) ++l;
                while (l <= r && C[tr][y] <= C[tr][q[r]]) --r;
                q[++r] = y;
                ret = max(ret, qry(x, y - (b - 2 - d + 1), x + a - 1, y + d) - C[tr][q[l]]);
            }
        }

        return ret;
    }

    void clean() {
        ms(qzh, 0);
    }
    int solve() {

        clean();
        cin >> m >> n >> a >> b >> c >> d;

        for (int i = 1; i <= m; ++i)
        for (int j = 1; j <= n; ++j) 
        scanf("%d", &orz[i][j]), qzh[i][j] = orz[i][j] + qzh[i - 1][j] + qzh[i][j - 1] - qzh[i - 1][j - 1];

        int ans = 0;

        ans = max(ans, work(a, b, c, d));

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

        return 0;
    }
}
int main() {
    flyinthesky::solve();
    return 0;
}
/*
4 3 4 3 2 1
2 2 3
4 5 1
3 1 6
4 8 6

4 3 3 3 1 1
2 2 3
4 5 1
3 1 6
4 8 6
*/
------ 本文结束 ------