Area1 https://blog.hatena.ne.jp/Area1/ Area1のif(memo[i][j]) https://area.hateblo.jp/ POJ データ構造 問題 0と1からなるnxmのマスが与えられる。この中に含まれる1のみからなるx軸とy軸に平行な長方形で最大の長方形の面積を求めよ。 やりかた ヒストグラム内の最大長方形の面積を求めるアルゴリズムを応用する。マスから一行読むごとにこのアルゴリズムを実施する。そのときにどれだけy軸方向に1が連続しているかを列ごとに蓄積しておくことで、その値をその行を読んだときのヒストグラムの高さとして考える事ができる。計算量O(nm)以下ソース。 int m, n; int h[2010]; int R[2010], L[2010]; int largest_hist(){ stack<int> S; for(l… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Farea.hateblo.jp%2Fentry%2F2018%2F06%2F07%2F161257" title="POJ 3494 Largest Submatrix of All 1’s - Area1のif(memo[i][j])" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> Hatena Blog https://hatena.blog 2018-06-07 16:12:57 rich https://area.hateblo.jp/entry/2018/06/07/161257 1.0 100%