Entries

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

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

コメント

コメントの投稿

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

トラックバック

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

SPOJ 7805 - Kitchen Robot [KITROB] (この記事を編集する[管理者用])

Source

ACM ICPC 2010, NEERC, Northern Subregional Contest
SPOJ 7805 [KITROB]

問題概要

2次元のx軸,y軸に平行な長方形のテーブルの上に,18個以下の瓶が置いてある.
ロボットは高々1個までしか同時に瓶を運べないとして,ビンを持ってテーブルの端に移動するとテーブルから瓶を落とせる.
全てのビンを落とすまでのロボットの移動経路の最小距離を求める問題.

解法

巡回セールスマン問題っぽくビットDPする.
予め,各ビン間の移動距離は計算しておく.
移動距離の計算は,テーブルの端を経由しなければいけないので,
それぞれのテーブルの辺に対して1点を対称に移動させて距離を計算すれば良い.

コメント

コメントの投稿

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

トラックバック

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

Appendix

Recent Articles

ブログ内検索

Ads


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