Entries

スポンサーサイト (この記事を編集する[管理者用])

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

コメント

コメントの投稿

コメントの投稿
管理者にだけ表示を許可する

トラックバック

トラックバック URL
http://rsujskf.blog32.fc2.com/tb.php/2311-18a86da0
この記事にトラックバックする(FC2ブログユーザー)

UVa 12481 - K-Neutral Rectangles (この記事を編集する[管理者用])

Source

First Bangladeshi Contest of 2012-2013 Season (2012-07-07)
UVa 12481

問題概要

N*M (1000*1000以下) のグリッドの各セルに整数が書かれている.
長方形の領域で,その領域内で隣合う2セルの差の絶対値がすべてK以下のものを考える.
そのような領域の面積の最大値を求める問題.
上下左右に隣合うものとする.

解法

各セルから,幅1だとすると,上に向かって何セル選んでも大丈夫か,
一つ右の列も選ぶ (幅2) とすると,何セル選んでも大丈夫か,をDPで前計算しておく.
すると,長方形領域の下の辺を固定すると,ヒストグラム中の最大長方形面積の問題に帰着される.
ALGORITHM NOTE http://algorithms.blog55.fc2.com/blog-entry-132.html 参照.

コメント

コメントの投稿

コメントの投稿
管理者にだけ表示を許可する

トラックバック

トラックバック URL
http://rsujskf.blog32.fc2.com/tb.php/2311-18a86da0
この記事にトラックバックする(FC2ブログユーザー)

Appendix

Recent Articles

ブログ内検索

Ads


(プライバシーポリシー)
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。