请管理员修复Latex
查看原帖
请管理员修复Latex
434929
Usada_Pekora楼主2021/11/24 12:50

题目描述:

小Z在供电公司找到了一份工作,刚上班就遇到了一个棘手的任务。

小Z所在的城市可以看成一个 n×mn \times m 的网格,第 ii 行第 jj 列的格子有电力需求 a[i][j]a[i][j] 。然而,供电公司能够供应的电力 uu 小于每格的电力需求之和。为此,供电公司不得不将城市划分成若干个区域,每个区域轮流断电,使得断电后剩余区域的电力需求之和不超过供电公司能够供应的电力。

为了方便起见,划分区域的方式很简单,每次将大区域横向或纵向划分成两个小区域,递归进行。

供电公司想尽可能减少市民的不满,因此需要小Z计算出最多能划分成多少个区域以及在此前提下能够剩余的最多电力(一种划分的剩余电力为每次断电后剩余电力的最小值),希望你帮帮他。

输入格式:

第一行包含三个整数 nnmmuu

接下来 nn 行,每行包含 mm 个整数,第 ii 行第 jj 个整数为 a[i][j]a[i][j]

说明/提示

【数据规模】

对于 60%60\% 的数据,n,m10n ,m \leq 10

对于 100%100\% 的数据, 1n,m32,1a[i][j]1001 \leq n,m \leq 32,1 \leq a[i][j] \leq 100

2021/11/24 12:50
加载中...