梦想星际舰队第26关 && EAOI#1 第一题美味披萨题解
梦想星际舰队第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
答案与解析
**** Hidden Message ***** 题目描述
有一个长为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++ 代码 isdkz 发表于 2023-9-9 16:35
题目描述
有一个长为n，宽为m的披萨，可以分为n行m列，每个格子的美味值是ai,j。现在你可以从中选择一块 ...
断了？ 好的，我要看一下我不会的题目， 看看 ？ 霉味披萨
sfqxx吃pi萨 这个像是前缀和 额外减小 发表于 2023-9-12 23:22
这个像是前缀和
二维 #include <bits/stdc++.h>
using namespace std;
int n, m, w, h;
long long a, 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);
}
}
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= m; ++j) {
a += a;
}
}
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= m; ++j) {
a += a;
}
}
for (int i = w; i <= n; ++i) {
for (int j = h; j <= m; ++j) {
long long tmp = a - a - a + a;
ans = max(ans, tmp);
}
}
printf("%lld\n", ans);
return 0;
}
你猜我怎么弄的 更新
页:
[1]