mini notes

競技プログラミングの解法メモを残していきます。

AOJ Courses DPL_3_B 最大長方形

問題:https://onlinejudge.u-aizu.ac.jp/problems/DPL_3_B

解答:https://onlinejudge.u-aizu.ac.jp/status/users/misora192/submissions/1/DPL_3_B/judge/5013955/C++14

解法: 参考サイト:
ALGORITHM NOTE 長方形探索: 最大長方形の面積 Largest Rectangle

まずはヒストグラム内の最大長方形を求める問題を解く。これはスタックを使ってうまくやる。
https://onlinejudge.u-aizu.ac.jp/status/users/misora192/submissions/1/DPL_3_C/judge/5013937/C++14

その後、各列ごとに上から0が何個連続しているかの2次元配列を作成する。その配列を行ごとにヒストグラムだと思ってみてゆき、そのヒストグラム内の最大長方形を求めればOK。