No Caffeine, No Life

プログラミング(主にPython)

AOJ DPL_3_B:最大長方形 (Largest Rectangle) 動的計画法

問題:

最大長方形 | 動的計画法 | Aizu Online Judge

解説:

与えられた盤面に対し、

  • 「(縦に見て)連続してきれいなマス目が何個並んでいるか」をカウント。それを「ヒストグラム」とみなして、
  • ヒストグラムに内接する最大の長方形を割り出す

という具合。なので、ヒストグラムを求める箇所と、その中の長方形を割り出す箇所の2つがキー。

詳細な解説は、下記を参照:

ALGORITHM NOTE ヒストグラム中の最大の長方形の面積

ALGORITHM NOTE 長方形探索: 最大長方形の面積 Largest Rectangle

 

解答例:

広告を非表示にする