問題リンク
問題概要
縦H、横Wマスのチョコレートがあり、一部のマスはホワイトチョコレートである。
このチョコを縦または横に一直線に切ることを何回か繰り返して、各部分に含まれるチョコレートがK個以下になるようにしたい。
切る回数の最小値はいくつか。
\(1 \leqq H \leqq 10\)
\(1 \leqq W \leqq 1000\)
解法
制約を見るとHが10以下と小さいので、横方向の切断は\(2^{H-1}\)通りを総当りできる。
例えばbit全探索で\(0～2^{H-1}\)までの値に対して「i番目のbitが立っている⇔上からi行目とi+1行目の間で切る」などとする。
横方向を決め打つと、縦方向に切る場所は貪欲に「左から見ていって、K個を超えた時点で切る」とすればよい。
提出
https://atcoder.jp/contests/abc159/submissions/11105114
感想
分割した後の実装が意外と重め。
