問題
N*Nの平面()に、AppleとPearが置かれている。空白のマスも存在する。ひとつのフルーツを取り出しそれを空のマスへ移動するという操作をK回(
)することができる。Appleで満たされる長方形の最大面積を求めよ。
解法
ある長方形をAppleで満たせるかを全探索する。与えられた平面の中に空白が一つでも存在すればフルーツを動かすことができる。ある長方形をAppleで満たすためのコストは、その中の空白の数eとPearの数pを用いてと表せる。
愚直に実装すると、計算量はとなる。これでも問題はないが空白、Pear、Appleの数を事前に計算しておくことで、
となる。
計算量
N: 平面のサイズ