[已解决]梦想星际舰队第26关 && EAOI#1 第一题美味披萨题解

isdkz

题目描述

有一个长为n，宽为m的披萨，可以分为n行m列，每个格子的美味值是ai,j。现在你可以从中选择一块长为w，宽为h的部分，使得这块部分的美味值之和最大，输出最大值。

输入格式

第一行四个整数n、m、w和h，表示披萨长、宽，以及最多能吃掉部分的长、宽。

接下来n行，每行m个数字，第i+1行第j列表示ai,j的值。

输出格式

输出美味值的最大值。

数据范围

对于100%的数据，1≤n,m≤1000，1≤w≤n，1≤h≤m，-1000≤ai,j≤1000，答案不超过64位整数类型。

样例

输入样例1：
4 4 2 2
1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 -100
输出样例1：
50

解题思路

1.前缀和

2.二维前缀和

3.滑动窗口

方法一：前缀和

计算前缀和，求出每个小矩形的和，然后遍历每个可能的大矩形，计算其中的和，取最大值即可。

时间复杂度

O(n^2)

空间复杂度

O(n^2)

C++ 代码

方法二：二维前缀和

计算二维前缀和，求出每个小矩形的和，然后遍历每个可能的大矩形，计算其中的和，取最大值即可。

时间复杂度

O(n^2)

空间复杂度

O(n^2)

C++ 代码

方法三：滑动窗口

由于只需要求出最大值，可以使用滑动窗口的思想，遍历每个可能的大矩形，计算其中的和，取最大值即可。

时间复杂度

O(n^2)

空间复杂度

O(1)

C++ 代码