Dividing Chocolate

题目描述

我们有一块被划分为 $H$ 行水平格子和 $W$ 列垂直格子的巧克力。 在从上数第 $i$ 行和从左数第 $j$ 列的位置处的格子 $(i, j)$ 如果 $S_{i,j}$ 为 $0$ 则为深色，如果 $S_{i,j}$ 为 $1$ 则为白色。 我们将通过若干次切割把巧克力分成若干块。在每次切割中，我们沿着从一端到另一端穿过格子边界的直线把整块巧克力切开。 需要切多少次才能使得每一块在切割后包含的白色格子数不超过 $K$？

输入格式

标准输入的格式如下： $H$ $W$ $K$ $S_{1,1}S_{1,2}...S_{1,W}$ $:$ $S_{H,1}S_{H,2}...S_{H,W}$

输出格式

输出使得每一块在切割后包含的白色格子数不超过 $K$ 所需的最小切割次数。

3 5 4
11100
10001
00111

2

3 5 8
11100
10001
00111

0

4 10 4
1110010010
1000101110
0011101001
1101000111

3

提示

$1 \leq H \leq 10$ $1 \leq W \leq 1000$ $1 \leq K \leq H \times W$ $S_{i,j}$ 是 $0$ 或 $1$。例如，在第 $1$ 行和第 $2$ 行之间切，以及在第 $3$ 行和第 $4$ 行之间切——如左图所示——是可行的。 注意我们不能按右图中的两种方式切割。
不需要切割。

标签: AtCoder|abc159E

来源

AtCoder|abc159E