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

zhangjinxuan

梦想星际舰队第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

题目描述

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

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

liuhongrun2022

看看

琅琊王朝

？

琅琊王朝

霉味披萨
sfqxx吃pi萨

额外减小

这个像是前缀和

zhangjinxuan

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

二维

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

更新