HAOI 2007 修築綠化帶
本文正體字版由OpenCC轉換
首先求出每個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