問題
高さH、幅Wの二次元配列が与えられる。各要素は0~9までの数字を持っている。この配列を縦と横に2つずつ直線を引いて9つのエリアに分割する。エリアの要素の総和がそのエリアの値となる。エリアの値の最小値が最大となる分割方法を見つけ、その時の値を求めよ。
解法
どこに線を引くかを全探索する。このまま、計算をするととなってしまう。
事前に(0,0)から(x, y)までの総和を計算しておくことでに減らすことができる。
計算量
高さH、幅Wの二次元配列が与えられる。各要素は0~9までの数字を持っている。この配列を縦と横に2つずつ直線を引いて9つのエリアに分割する。エリアの要素の総和がそのエリアの値となる。エリアの値の最小値が最大となる分割方法を見つけ、その時の値を求めよ。
どこに線を引くかを全探索する。このまま、計算をするととなってしまう。
事前に(0,0)から(x, y)までの総和を計算しておくことでに減らすことができる。