FC2ブログ

Entries

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

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

コメント

コメントの投稿

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

トラックバック

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

ZJU 3222 - Coverage (この記事を編集する[管理者用])

Source
ZOJ Monthly, July 2009 (2009-07-19)
ZJU 3222

問題概要
無限大の大きさのグリッドの100×100以下の部分以外は全部0で埋め尽くされている.
100×100以下の部分には整数が入っている.
縦X,横Yの大きさの長方形を2つの長方形に分割して,それぞれを重なっても良いのでグリッドの上に乗せる.
回転してはいけない.
長方形の重なっている部分の数字の和を最大化する問題.
重なっている部分は重複して数える.

解法
適当にDPっぽいこと(和を先に計算しておく)をすれば,後は全ての長方形の分け方とどこに置くかを全て調べてお終い.

コメント

コメントの投稿

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

トラックバック

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

Appendix

Recent Articles

ブログ内検索

Ads


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