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

zhangjinxuan · 发表于 2023-9-9 16:35:33

马上注册，结交更多好友，享用更多功能^_^

您需要登录才可以下载或查看，没有账号？立即注册

x

梦想星际舰队第26关 && EAOI #1 题解

第一题：美味披萨

题目描述
sfqxx 去披萨店吃披萨。

店主拿来了一块长方形的披萨，披萨可以分为长为 n 块，宽为 m 块，i 行 j 列块的美味值是披萨可以分为长为 a i,j（可能是负数）。

sfqxx 只能吃掉一块长为 w ，高为 h 的部分。

而 sfqxx 希望可以吃到最美味的披萨（美味值之和），希望你帮帮他。

形式化的语言来说，你要找到一对整数 (x,y)(1≤x≤n-w+1,1≤y≤m−h+1)，请求出：∑_(i=x)^(x+w−1) ∑_(i=y)^(y+h−1)A i,j的最大值。

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

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

输出格式
输出美味值的最大值。

输入输出样例
输入 #1

4 4 2 2
1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 -100

复制代码

输出 #1

50

复制代码

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

其他说明
本题非原创，是 Ewan_Ahiouy 原创题目，本帖子是代发题解。
测试链接：https://www.luogu.com.cn/problem/T372793

答案与解析

游客，如果您要查看本帖隐藏内容请回复

[/hide]

最佳答案

月排行榜 / 总排行榜

hveagle

2023-12-12 21:07:22

#include <bits/stdc++.h>
using namespace std;
int n, m, w, h;
long long a[1001][1001], ans = -1ll << 60;
int main() {
scanf("%d%d%d%d", &n, &m, &w, &h);
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= m; ++j) {
scanf("%lld", &a[i][j]);
}
}
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= m; ++j) {
a[i][j] += a[i][j - 1];
}
}
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= m; ++j) {
a[i][j] += a[i - 1][j];
}
}
for (int i = w; i <= n; ++i) {
for (int j = h; j <= m; ++j) {
long long tmp = a[i][j] - a[i - w][j] - a[i][j - h] + a[i - w][j - h];
ans = max(ans, tmp);
}
}
printf("%lld\n", ans);
return 0;
}

复制代码

你猜我怎么弄的

跳转到最佳答案楼层

isdkz · 发表于 2023-9-9 16:35:46

题目描述

有一个长为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++ 代码

歌者文明清理员 · 发表于 2023-9-9 16:42:32

isdkz 发表于 2023-9-9 16:35
题目描述

有一个长为n，宽为m的披萨，可以分为n行m列，每个格子的美味值是ai,j。现在你可以从中选择一块 ...

断了？

sfqxx · 发表于 2023-9-9 17:12:52

好的，我要看一下我不会的题目，

liuhongrun2022 · 发表于 2023-9-9 17:57:53

看看

琅琊王朝 · 发表于 2023-9-10 14:25:55

琅琊王朝 · 发表于 2023-9-10 14:26:50

霉味披萨
sfqxx吃pi萨

额外减小 · 发表于 2023-9-12 23:22:41

这个像是前缀和

zhangjinxuan · 发表于 2023-9-13 12:56:31

额外减小发表于 2023-9-12 23:22
这个像是前缀和

二维

hveagle · 发表于 2023-12-12 21:07:22

这个最佳答案由 hveagle 给出，感谢 hveagle 的回答。

单击隐藏图章

#include <bits/stdc++.h>
using namespace std;
int n, m, w, h;
long long a[1001][1001], ans = -1ll << 60;
int main() {
scanf("%d%d%d%d", &n, &m, &w, &h);
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= m; ++j) {
scanf("%lld", &a[i][j]);
}
}
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= m; ++j) {
a[i][j] += a[i][j - 1];
}
}
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= m; ++j) {
a[i][j] += a[i - 1][j];
}
}
for (int i = w; i <= n; ++i) {
for (int j = h; j <= m; ++j) {
long long tmp = a[i][j] - a[i - w][j] - a[i][j - h] + a[i - w][j - h];
ans = max(ans, tmp);
}
}
printf("%lld\n", ans);
return 0;
}

复制代码

你猜我怎么弄的

hveagle · 发表于 2023-12-25 21:09:43

更新

账号		自动登录	找回密码
密码			立即注册

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

马上注册，结交更多好友，享用更多功能^_^

本帖被以下淘专辑推荐:

评分

浏览过的版块