目录
一、3194. 最小元素和最大元素的最小平均值
二、3195. 包含所有 1 的最小矩形面积 I
三、3196. 最大化子数组的总成本
四、3197. 包含所有 1 的最小矩形面积 II
博主在比赛时只过了前两题。剩下跟着灵神做，来自视频：
【状态机 DP【力扣周赛 403】】 https://www.bilibili.com/video/BV1MZ421M74P/?share_source=copy_web&vd_source=dc0e55cfae3b304619670a78444fd795
一、3194. 最小元素和最大元素的最小平均值
1.自写：
class Solution:
def minimumAverage(self, nums: List[int]) -> float:
nums.sort()
ans = inf
l, r = 0, len(nums) - 1
while l <= r:
ans = min(ans, nums[l] + nums[r])
l += 1
r -= 1
return ans / 22.灵神：
class Solution:
def minimumAverage(self, nums: List[int]) -> float:
n = len(nums)
nums.sort()
ans = inf
for i in range(n // 2):
j = n - 1 - i
ans = min(ans, nums[i] + nums[j])
return ans / 2二、3195. 包含所有 1 的最小矩形面积 I
1.自写：
我每次一遇到这种题，就只一股脑用前缀和（笑哭）。
class Solution:
def minimumArea(self, grid: List[List[int]]) -> int:
# 前缀和
n, m = len(grid), len(grid[0])
mx = 0
ans = 0
flag = (0, 0)
add = [[0 for _ in range(m + 1)] for _ in range(n + 1)]
for i in range(n):
for j in range(m):
add[i + 1][j + 1] = add[i][j + 1] + add[i + 1][j] - add[i][j] + grid[i][j]
if add[i + 1][j + 1] > mx:
mx = add[i + 1][j + 1]
ans = (i + 1) * (j + 1)
flag = ((i + 1), (j + 1))
# 找到前面空的
i = 1
while i <= n:
if add[i][-1] != 0:
break
i += 1
j = 1
while j <= m:
if add[-1][j] != 0:
break
j += 1
ans -= (i - 1) * flag[1] + (j - 1) * flag[0] - (i - 1) * (j - 1)
return ans2.灵神：
class Solution:
def minimumArea(self, grid: List[List[int]]) -> int:
# 边界
left, right = len(grid[0]), 0
up, down = len(grid), 0
for i, row in enumerate(grid):
for j, x in enumerate(row):
if x:
left = min(left, j)
right = max(right, j)
up = min(up, i)
down = i # 从上到下遍历
return (down - up + 1) * (right - left + 1)三、3196. 最大化子数组的总成本
当时第一反应是dp，但是我当时想的是前缀，没能解决。
灵神：
附一个自己画的状态转移的简单图解：
（1）递归
class Solution:
def maximumTotalCost(self, nums: List[int]) -> int:
# dp
# 后缀
# 递归
@cache
def dfs(i: int, j: int) -> int:
if i == len(nums):
return 0
if j == 0:
return dfs(i + 1, 1) + nums[i]
return max(dfs(i + 1, 1) + nums[i], dfs(i + 1, 0) - nums[i])
return dfs(0, 0) # 第一位肯定为正(2)递推，一比一翻译
class Solution:
def maximumTotalCost(self, nums: List[int]) -> int:
# dp
# 后缀
# 递推，一比一翻译
n = len(nums)
f = [[0, 0] for _ in range(n + 1)]
for i in range(n - 1, -1, -1):
f[i][0] = f[i + 1][1] + nums[i]
f[i][1] = max(f[i + 1][1] + nums[i], f[i + 1][0] - nums[i])
return f[0][0]（3）递推，滑动窗口
class Solution:
def maximumTotalCost(self, nums: List[int]) -> int:
# dp
# 后缀
# 递推，滑动窗口
n = len(nums)
j0, j1 = 0, 0
# 切片nums[::-1]，会消耗额外空间
# reversed()生成迭代器，不会消耗额外空间
for x in reversed(nums):
j0, j1 = j1 + x, max(j1 + x, j0 - x)
return j0四、3197. 包含所有 1 的最小矩形面积 II
听了讲解后自己写的代码，旋转90度的代码参考视频。
class Solution:
def minimumSum(self, grid: List[List[int]]) -> int:
n, m = len(grid), len(grid[0])
return min(self.f(grid, n, m), self.f(self.rotate(grid, n, m), m, n))
def cover(self, grid: List[List[int]], left: int, right: int, up: int, down: int) -> int:
# 计算最小面积
# 闭区间
# 注意区域内可能没有1，区别第二题
# 要么返回时判断，要么初始化时设置大一点
l, r = right, left
u, d = down, up
for i in range(up, down + 1):
for j in range(left, right + 1):
if grid[i][j]:
l = min(l, j)
r = max(r, j)
u = min(u, i)
d = i
return (r - l + 1) * (d - u + 1) if r >= l and d >= u else 0
def f(self, grid: List[List[int]], n: int, m: int) -> int:
ans = 901
# 划分横着三个区域
if n >= 3:
for line1 in range(n - 2):
for line2 in range(line1 + 1, n - 1):
m1 = self.cover(grid, 0, m - 1, 0, line1)
m2 = self.cover(grid, 0, m - 1, line1 + 1, line2)
m3 = self.cover(grid, 0, m - 1, line2 + 1, n - 1)
ans = min(ans, m1 + m2 + m3)
if n >= 2 and m >= 2:
for line1 in range(n - 1):
for line2 in range(m - 1):
# 划分上横下二区域
m1 = self.cover(grid, 0, m - 1, 0, line1)
m2 = self.cover(grid, 0, line2, line1 + 1, n - 1)
m3 = self.cover(grid, line2 + 1, m - 1, line1 + 1, n - 1)
ans = min(ans, m1 + m2 + m3)
# 划分下横上二区域
m1 = self.cover(grid, 0, line2, 0, line1)
m2 = self.cover(grid, line2 + 1, m - 1, 0, line1)
m3 = self.cover(grid, 0, m - 1, line1 + 1, n - 1)
ans = min(ans, m1 + m2 + m3)
return ans
def rotate(self, grid: List[List[int]], n: int, m: int) -> List[List[int]]:
# 顺时针旋转90度
ans = [[0 for _ in range(n)] for _ in range(m)]
for i in range(n):
for j in range(m):
ans[j][n - 1 - i] = grid[i][j]
return ans参考评论区评论（. - 力扣（LeetCode）），事先使用一个覆盖框预处理（想起了R-CNN），修改代码如下：
class Solution:
def minimumSum(self, grid: List[List[int]]) -> int:
n, m = len(grid), len(grid[0])
return min(self.f(grid, n, m), self.f(self.rotate(grid, n, m), m, n))
def cover(self, grid: List[List[int]], left: int, right: int, up: int, down: int) -> int:
# 计算最小范围
# 闭区间
l, r = right, left
u, d = down, up
for i in range(up, down + 1):
for j in range(left, right + 1):
if grid[i][j]:
l = min(l, j)
r = max(r, j)
u = min(u, i)
d = i
return l, r, u, d
def minArea(self, grid: List[List[int]], l: int, r: int, u: int, d: int) -> int:
# 注意区域内可能没有1，区别第二题
# 要么返回时判断，要么初始化时设置大一点
l, r, u, d = self.cover(grid, l, r, u, d) # 找出最小覆盖范围
return (r - l + 1) * (d - u + 1) if r >= l and d >= u else 0
def f(self, grid: List[List[int]], n: int, m: int) -> int:
# 先事先筛选一个大矩形框
left, right, up, down = self.cover(grid, 0, m - 1, 0, n - 1)
# left -> 0, right -> m - 1, up -> 0, down -> n - 1
ans = 901
# 划分横着三个区域
if n >= 3:
for line1 in range(up, down - 1):
for line2 in range(line1 + 1, down):
m1 = self.minArea(grid, left, right, up, line1)
m2 = self.minArea(grid, left, right, line1 + 1, line2)
m3 = self.minArea(grid, left, right, line2 + 1, down)
ans = min(ans, m1 + m2 + m3)
if n >= 2 and m >= 2:
for line1 in range(up, down):
for line2 in range(left, right):
# 划分上横下二区域
m1 = self.minArea(grid, left, right, up, line1)
m2 = self.minArea(grid, left, line2, line1 + 1, down)
m3 = self.minArea(grid, line2 + 1, right, line1 + 1, down)
ans = min(ans, m1 + m2 + m3)
# 划分下横上二区域
m1 = self.minArea(grid, left, line2, up, line1)
m2 = self.minArea(grid, line2 + 1, right, up, line1)
m3 = self.minArea(grid, left, right, line1 + 1, down)
ans = min(ans, m1 + m2 + m3)
return ans
def rotate(self, grid: List[List[int]], n: int, m: int) -> List[List[int]]:
# 顺时针旋转90度
ans = [[0 for _ in range(n)] for _ in range(m)]
for i in range(n):
for j in range(m):
ans[j][n - 1 - i] = grid[i][j]
return ans灵神还有一种使用dp进行预处理降低时间复杂度的方法，但是我没学，感觉这暂时不是我能学会的，感兴趣的可以看他的题解（. - 力扣（LeetCode））。
完
感谢你看到这里！一起加油吧！
