B3724
一扶苏一
·
·
题解
[语言月赛202303] Carrot Harvest G 题解
Source & Knowledge
2023 年 3 月语言月赛，由洛谷网校入门计划/基础计划提供。
本题考察循环结构。
文字题解
题目大意
给出 n 行 m 列共 n \times m 个数，每个数要么是 0 要么是 1，形成了一个矩形。
选择一个包含数字的数量最少的矩形区域，满足这个区域里的数字之和不低于 k。
### 解析
考虑枚举所有可能的矩形区域：
用一个两重的 for 循环 $i,j$ 枚举矩形区域左上角所在的行和列，再用一个两重的 for 循环 $x, y$ 枚举矩形区域右下角所在的行和列。这样可以唯一确定所求的矩形区域。注意因为 $(i,j)$ 在 $(x, y)$ 的右下角，所以应该满足 $x \geq i$，$y \geq j$。
枚举出矩形区域后，可以继续在里面嵌套两层循环，求出区域内部的数字之和。
```cpp
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= m; ++j) // i 和 j 枚举左上角
for (int x = i; x <= n; ++x) // x>=i 所以从 i 开始枚举
for (int y = j; y <= m; ++y) {// x 和 y 枚举右下角
int sum = 0; // sum 表示当前矩形区域的和
for (int p = i; p <= x; ++p)
for (int q = j; q <= y; ++q)
sum += a[i];
}
```
求出 $sum$ 后，可以把 $sum$ 和 $k$ 作比较。如果 $sum \geq k$，则比较一下当前区域所包含的数字数，尝试更新答案。显然当前区域包含的数字数是 $(x - i + 1) \times (y - j + 1)$。
```cpp
if (sum >= k) ans = min(ans, (x - i + 1) * (y - j + 1));
```
最后输出答案，就完成了本题。
## 视频题解
## 视频题解
**完整代码请在视频中观看**。
