Rockdu's Blog

题目描述

为了增添公园的景致，现在需要在公园中修筑一个花坛，同时在画坛四周修建一片绿化带，让花坛被绿化带围起来。

如果把公园看成一个M*N的矩形，那么花坛可以看成一个C*D的矩形，绿化带和花坛一起可以看成一个A*B的矩形。

如果将花园中的每一块土地的“肥沃度”定义为该块土地上每一个小块肥沃度之和，那么，

绿化带的肥沃度=A*B块的肥沃度-C*D块的肥沃度

为了使得绿化带的生长得旺盛，我们希望绿化带的肥沃度最大。

输入输出格式

第一行有6个正整数M,N,A,B,C,D

接下来一个M*N的数字矩阵，其中矩阵的第i行j列元素为一个整数Xij,表示该花园的第i行第j列的土地“肥沃度”。

一个正整数，表示绿化带的最大肥沃程度。

输入输出样例

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

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

容易发现其实就是对每一个可以放置a*b矩形的位置求出内部一个权值最小矩形。

二维最值显然可以树套树，但是这里不需要，没有修改操作并且每次查询的矩形大小一直相等，容易想到单调队列。

那么我们用单调队列套单调队列。先把所有c*d大小矩形的内部和归到左上角。底层用n个单调队列移着走，并且更新行上固定宽度的最小值。每移到新的一列统计答案，发现也是求固定长度区间最小值，再用一个单调队列移出答案就行了。

边界有点恶心，一定看清楚再写。

#include<cstdio>
#include<queue>
#include<cstring>
#include<algorithm>
#define LL long long
using namespace std;
const int maxn = 1e3 + 5;
int mp[maxn][maxn], n, m, a, b, c, d, ans;
int sum[maxn][maxn], h, w, nowc, mn[maxn];
typedef pair<int, int > pii;
deque<pii > q[maxn], nq;

int GetSum(int x1, int y1, int x2, int y2) {
    return sum[x2][y2] - sum[x1 - 1][y2] - sum[x2][y1 - 1] + sum[x1 - 1][y1 - 1];
}

void push(deque<pii > & q, int pos, int x, int l) {
    while(!q.empty() && q.front().second <= pos - l) 
        q.pop_front();
    while(!q.empty() && q.back().first > x) 
        q.pop_back();
    q.push_back(make_pair(x, pos));
}

void Move(int col) {
    for(register int i = 1; i <= n - c + 1; ++i) {
        push(q[i], col, mp[i][col], w - 1), mn[i] = q[i].front().first;
        //putchar('*');
    }
    //putchar('\n');
}

int main() {
    scanf("%d%d%d%d%d%d", &n, &m, &a, &b, &c, &d);
    for(register int i = 1; i <= n; ++i)
        for(register int j = 1; j <= m; ++j)
            scanf("%d", &mp[i][j]), sum[i][j] += mp[i][j];
    for(register int i = 1; i <= n; ++i)
        for(register int j = 1; j <= m; ++j)
            sum[i][j] += sum[i][j - 1] + sum[i - 1][j] - sum[i - 1][j - 1];
    memset(mp, 0, sizeof(mp));
    for(register int i = 1; i <= n - c + 1; ++i)
        for(register int j = 1; j <= m - d + 1; ++j)
            mp[i][j] = GetSum(i, j, i + c - 1, j + d - 1);
    h = a - c, w = b - d;
    int tp = 0, tp2 = 0;
    for(register int i = 1; i <= m - b + 1; ++i) {
        while(tp < i + w - 1) Move(++tp);
        nq.clear(), tp2 = 0;
        for(register int j = 1; j <= n - a + 1; ++j) {
            while(tp2 < j + h - 1) 
                ++tp2, push(nq, tp2, mn[tp2], h - 1);
            ans = max(GetSum(j, i, j + a - 1, i + b - 1) - nq.front().first, ans);
        }
    }
    printf("%d", ans);
    return 0;
}