题目翻译
有一个 $H\times W$ 的矩阵，切若干次，使得每一块中 $1$ 个数 $\leq k$，只能一切到底，问最少用几刀。
题目思路
直接暴力枚举每一行每一列绝对不行，复杂度 $\mathcal O(2^{H+W})$。
我们发现 $H$ 很小，我们可以枚举 $H$ 在哪里切割，复杂度 $\mathcal O(2^H)$。其实最多只有 $H-1$ 刀，为了方便描述，统一用 $H$。
接着，我们对于 $W$ 考虑贪心，每一块有尽量多的 $1$，最后肯定花费最小，也是可以证明的。
综上所述，我们枚举 $2^H$ 种方案，接着扫一遍 $W$ 确定切割次数。
时间复杂度 $\mathcal O(2^H\times W\times H)$，可以通过此题。
但是还不完美，如果 $H\leq 15,W\leq 10^6$，明显是会炸掉的。
我们扫 $W$ 时，这里 $1$ 个数肯定是单调不增的，可以考虑进行二分或者倍增来找。这一段的时间复杂度一下子变成了 $\mathcal O(\log W)$，总时间复杂度 $\mathcal O(2^H\times \log W\times H)$。
但上述做法在面对全是 $1$ 时，每次只能前进一步，实际上会退化成 $\mathcal O(W)$。其余数据效果比最初做法时间上较佳。
完整代码
代码很长，不贴了，发个链接。
