Beyond the Void
BYVoid
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&lt;=M,N&lt;=50
100%的數據,1&lt;=M,N&lt;=1000,1&lt;=A&lt;=M,1&lt;=B&lt;=N,1&lt;=C&lt;=A-2,1&lt;=D&lt;=B-2,1&lt;=“肥沃度”&lt;=100</div>

上次修改時間 2017-02-03

相關日誌