题目描述
为了增添公园的景致，现在需要在公园中修筑一个花坛，同时在画坛四周修建一片绿化带，让花坛被绿化带围起来。
如果把公园看成一个M * N的矩形，那么花坛可以看成一个C * D的矩形，绿化带和花坛一起可以看成一个A * B的矩形。
如果将花园中的每一块土地的“肥沃度”定义为该块土地上每一个小块肥沃度之和，那么，
绿化带的肥沃度=A * B块的肥沃度-C * D块的肥沃度
为了使得绿化带的生长得旺盛，我们希望绿化带的肥沃度最大。
输入输出格式
输入格式：
第一行有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
(e[i][j])表示以([i,j])为右下角的(C*D)的矩形的权值和，然后用单调队列求出(g[i][j])表示([i,j])为右下角(A*B)的矩阵内(C*D)最靠下一行中值的最小值，第二遍单调队列求出([i,j])为右下角(A*B)的矩阵内全部(C*D)中值的最小值，扫一遍统计答案
#include<iostream>
#include<cstdio>
#include<deque>
#define M (b-d)
#define N (a-c)
using namespace std;
deque <pair<int,int> >q;
int i,m,n,j,k,a,b,c,d,z[1001][1001],cc[1001][1001],e[1001][1001],g[1001][1001],f[1001][1001],ans;
int main()
{
scanf("%d%d%d%d%d%d",&n,&m,&a,&b,&c,&d);
for(i=1;i<=n;i++)
for(j=1;j<=m;j++)
{
scanf("%d",&z[i][j]);
cc[i][j]=z[i][j]+cc[i-1][j]+cc[i][j-1]-cc[i-1][j-1];
if((i>=c)&&(j>=d)) e[i][j]=cc[i][j]-cc[i-c][j]-cc[i][j-d]+cc[i-c][j-d];
}
for(i=c;i<=n;i++)
{
while(q.size()) q.pop_back();
for(j=d;j<=m;j++)
{
if(q.size()&&(j-q.back().second>=M)) q.pop_back();
if(q.size())g[i][j]=q.back().first;
while(q.size()&&(q.front().first>e[i][j])) q.pop_front();
q.push_front(make_pair(e[i][j],j));
}
}
for(j=d;j<=m;j++)
{
while(q.size()) q.pop_back();
for(i=c;i<=n;i++)
{
if(q.size()&&(i-q.back().second>=N)) q.pop_back();
if(q.size())f[i][j]=q.back().first;
while(q.size()&&(q.front().first>g[i][j])) q.pop_front();
q.push_front(make_pair(g[i][j],i));
}
}
for(i=a;i<=n;i++)
for(j=b;j<=m;j++)
ans=max(ans,cc[i][j]-cc[i-a][j]-cc[i][j-b]+cc[i-a][j-b]-f[i][j]);
printf("%d",ans);
}