自动搬运

查看原文

来自洛谷，原作者为

	一扶苏一 休息结束。邮箱 yifusuyi@qq.com

搬运于2025-08-24 21:14:38，当前版本为作者最后更新于2018-05-27 21:07:35，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

[语言月赛202303] Carrot Harvest G 题解

Source & Knowledge

2023 年 3 月语言月赛，由洛谷网校入门计划/基础计划提供。

本题考察循环结构。

文字题解

题目大意

给出 $n$ 行 $m$ 列共 $n \times m$ 个数，每个数要么是 $0$ 要么是 $1$，形成了一个矩形。

选择一个包含数字的数量最少的矩形区域，满足这个区域里的数字之和不低于 $k$。

$1 \leq n, m \leq 20$，$1 \leq k \leq 400$。

解析

考虑枚举所有可能的矩形区域：

用一个两重的 for 循环 $i,j$ 枚举矩形区域左上角所在的行和列，再用一个两重的 for 循环 $x, y$ 枚举矩形区域右下角所在的行和列。这样可以唯一确定所求的矩形区域。注意因为 $(i,j)$ 在 $(x, y)$ 的右下角，所以应该满足 $x \geq i$，$y \geq j$。

枚举出矩形区域后，可以继续在里面嵌套两层循环，求出区域内部的数字之和。

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)$。

if (sum >= k) ans = min(ans, (x - i + 1) * (y - j + 1));

最后输出答案，就完成了本题。

视频题解

视频题解

完整代码请在视频中观看。