自动搬运

查看原文

来自洛谷，原作者为

	nosta 星空の下はダンスホール

搬运于2025-08-24 21:35:17，当前版本为作者最后更新于2018-12-14 20:54:19，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

说看代码理解的你们够了

相信泥萌都是从试炼场刷过来的吧？所以这道题泥萌一定做过了。回顾一下怎么做的呢？二维的单调队列做法：先就某一维上对原始数据进行处理，在对另一维上对前一维的数据进行处理，就得到了所需要的东西。

回到这题，也是同样的做法，下边是我解题时的思路：

1. 预处理出以A[i,j]、B[i,j]分别为右下角的花坛(C*D)、大矩形(A*B)的肥沃度和

2. 按行，利用单调队列求出P[i,j]=以A[i, j-B+1+D→j-1]中的最小值，即以(i, j-B+1+D→j-1)为右下角的花坛肥沃度的最小值。

3. 按列，利用单调队列求出Q[i,j]=以P[i-A+1+C→i-1, j]中的最小值，即以(i-A+1+C→i-1, j-B+1+D→j-1) 为右下角的花坛肥沃度的最小值，显然，这些花坛包含在了以(i,j)为右下角的大矩形中；

4. 显然B[i,j]-Q[i,j]即为以(i,j)为右下角的绿化带的最大肥沃值。

时间复杂度 O(nm)。代码实现中n、m与题意是反的。欢迎来hack

#include <bits/stdc++.h>
using namespace std;

const int N=1005;

int n,m,A,B,C,D,hd,tl,q[N];
int s[N][N],a[N][N],b[N][N],P[N][N],Q[N][N];

int main() {
	scanf("%d%d %d%d%d%d",&n,&m,&A,&B,&C,&D);
	for(int i=1; i<=n; ++i) {
		for(int j=1; j<=m; ++j) {
			scanf("%d",&s[i][j]);
			s[i][j]=s[i][j]+s[i-1][j]+s[i][j-1]-s[i-1][j-1];
		}
	}
	for(int i=C+1; i<n; ++i) {
		for(int j=D+1; j<m; ++j) {
			a[i][j]=s[i][j]-s[i-C][j]-s[i][j-D]+s[i-C][j-D];
		}
	}
	for(int i=A; i<=n; ++i) {
		for(int j=B; j<=m; ++j) {
			b[i][j]=s[i][j]-s[i-A][j]-s[i][j-B]+s[i-A][j-B];
		}
	}
	for(int i=C+1; i<n; ++i) {
		hd=1, tl=0;
		for(int j=D+1; j<m; ++j) {
			while(hd<=tl && q[hd]<j-B+2+D) hd++; //*
			while(hd<=tl && a[i][q[tl]]>=a[i][j]) tl--;
			q[++tl]=j;
			if(j>=B-1) P[i][j+1]=a[i][q[hd]];
		}
	}
	for(int j=B; j<=m; ++j) {
		hd=1, tl=0;
		for(int i=C+1; i<n; ++i) {
			while(hd<=tl && q[hd]<i-A+2+C) hd++;
			while(hd<=tl && P[q[tl]][j]>=P[i][j]) tl--;
			q[++tl]=i;
			if(i>=A-1) Q[i+1][j]=P[q[hd]][j];
		}
	}
	int ans=0;
	for(int i=A; i<=n; ++i) {
		for(int j=B; j<=m; ++j) {
			ans=max(ans,b[i][j]-Q[i][j]);
		}
	}
	printf("%d\n",ans);
	return 0;
} 

* 原来的区间[j-B+1+D, j-1]是对于j来说的；但此处我们在j的位置时更新j+1，所以范围调整为[j-B+2+D, j]。下同。