HAOI 2007 修筑绿化带
首先求出每个AB的矩阵的数值和，以及每个CD的矩阵的数值和，用递推的方法可以达到O(NM)。 接下来，求出每个(A-2)(B-2)范围内最小的CD的矩阵（因为花坛不能建在绿化带边缘），可以用单调队列的方法递推，时间复杂度为O(NM)。最后对于每个AB的局限，求出其范围内最小的花坛，时间复杂度为O(NM)，总的时间复杂度就是O(N*M)。
这道题本身不难，关键在仔细处理好递推的边界。
/*
* Problem: HAOI2007 parterre
* Author: Guo Jiabao
* Time: 2009.4.20 10:32
* State: Solved
* Memo: 动态规划 单调队列 矩阵压缩
*/
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
const int MAXN=1001;
using namespace std;
struct MonoQueue
{
struct MQElement
{
int id,value;
}Q[MAXN];
int head,tail;
void clear(){head=0;tail=-1;}
void ins(int value,int id)
{
while(tail>=head && value<Q[tail].value) tail--;
Q[++tail].value=value;
Q[tail].id=id;
}
int getmin(int id)
{
while (Q[head].id<id) head++;
return Q[head].value;
}
}MQ;
struct Matrix
{
int N,M;
int X[MAXN][MAXN];
}Green,Flower,FM;
int N,M,A,B,C,D,EN,EM,Ans=0;
int X[MAXN][MAXN],Y[MAXN][MAXN];
void init()
{
int i,j;
freopen("parterre.in","r",stdin);
freopen("parterre.out","w",stdout);
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",&X[i][j]);
}
void solve()
{
int i,j;
Green.N=N+1-A; Green.M=M+1-B;
Flower.N=N+1-C; Flower.M=M+1-D;
EN=A-2-C+1; EM=B-2-D+1;
FM.N=Flower.N+1-EN; FM.M=Flower.M+1-EM;
for (j=1;j<=M;j++)
{
Y[1][j]=0;
for (i=1;i<=A;i++)
Y[1][j]+=X[i][j];
for (i=2;i+A-1<=N;i++)
Y[i][j]=Y[i-1][j]-X[i-1][j]+X[i+A-1][j];
}
for (i=1;i<=Green.N;i++)
{
Green.X[i][1]=0;
for (j=1;j<=B;j++)
Green.X[i][1]+=Y[i][j];
for (j=2;j<=Green.M;j++)
Green.X[i][j]=Green.X[i][j-1]-Y[i][j-1]+Y[i][j+B-1];
}
for (j=1;j<=M;j++)
{
Y[1][j]=0;
for (i=1;i<=C;i++)
Y[1][j]+=X[i][j];
for (i=2;i+C-1<=N;i++)
Y[i][j]=Y[i-1][j]-X[i-1][j]+X[i+C-1][j];
}
for (i=1;i<=Flower.N;i++)
{
Flower.X[i][1]=0;
for (j=1;j<=D;j++)
Flower.X[i][1]+=Y[i][j];
for (j=2;j<=Flower.M;j++)
Flower.X[i][j]=Flower.X[i][j-1]-Y[i][j-1]+Y[i][j+D-1];
}
for (j=1;j<=Flower.M;j++)
{
MQ.clear();
for (i=1;i<=EN-1;i++)
MQ.ins(Flower.X[i][j],i);
for (i=1;i<=FM.N;i++)
{
MQ.ins(Flower.X[i+EN-1][j],i+EN-1);
Y[i][j]=MQ.getmin(i);
}
}
for (i=1;i<=FM.N;i++)
{
MQ.clear();
for (j=1;j<=EM-1;j++)
MQ.ins(Y[i][j],j);
for (j=1;j<=FM.M;j++)
{
MQ.ins(Y[i][j+EM-1],j+EM-1);
FM.X[i][j]=MQ.getmin(j);
}
}
for (i=1;i<=Green.N;i++)
{
for (j=1;j<=Green.M;j++)
{
int R=Green.X[i][j];
R-=FM.X[i+1][j+1];
if (R>Ans)
Ans=R;
}
}
}
int main()
{
init();
solve();
printf("%dn",Ans);
return 0;
}
<div class="MainText">
<a href="http://www.ruvtex.cn/cogs/problem/pdetail.php?pid=24" target="_blank">http://www.ruvtex.cn/cogs/problem/pdetail.php?pid=24</a>
<strong>修筑绿化带</strong>
<strong>【问题描述】</strong>
为了增添公园的景致，现在需要在公园中修筑一个花坛，同时在画坛四周修建一片绿化带，让花坛被绿化带围起来。
如果把公园看成一个M*N的矩形，那么花坛可以看成一个C*D的矩形，绿化带和花坛一起可以看成一个A*B的矩形。
如果将花园中的每一块土地的“肥沃度”定义为该块土地上每一个小块肥沃度之和，那么，
绿化带的肥沃度=A*B块的肥沃度-C*D块的肥沃度
为了使得绿化带的生长得旺盛，我们希望绿化带的肥沃度最大。
<strong>【输入】</strong>:
第一行有6个正整数M,N,A,B,C,D
接下来一个M*N的数字矩阵，其中矩阵的第i行j列元素为一个整数Xij,表示该花园的第i行第j列的土地“肥沃度”。
<strong>【输出】</strong>:
一个正整数，表示绿化带的最大肥沃程度。
<strong>【输入输出样例】</strong>
<strong>parterre.in </strong>
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
<strong>parterre.out </strong>
132
<strong>【数据范围】</strong>
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</div>
上次修改时间 2017-02-03