Entries

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

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

コメント

コメントの投稿

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

トラックバック

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

UVa 12540 - Warp Speed II (この記事を編集する[管理者用])

Source

An Asian Regional contest to be decided, ACM ICPC Hatyai Regional Contest 2012 Semilive (2012-11-18)
UVa 12540

問題概要

ある宇宙船はN個 (100以下) の状態に変形ができる.状態を0~N-1で番号付ける.
時間1経過ごとに1回変形(もしくはその形態を維持)でき,状態iから状態jに変形するコストが与えられる.(維持にもコストがかかる)
その宇宙船はM個 (1000以下) のアクションが出来る.アクションを0~M-1で番号付ける.
各状態において,各アクションを行うのに必要なコストが与えられる.ただし状態0では何もアクションできない.
クエリが幾つか与えられる.
各クエリは,アクションの列 X[1], X[2], ... X[k] (kは1000以下) で,時間iでアクションX[i]を行わなければならない.
また,時間0,時間k+1では状態0にならなければならない.
最小コストと,それを満たす変形の列を求める問題.複数あるなら変形の列は辞書順最小のものを求める.
与えられるコストは全部100以下.

解法

DP or メモ化再帰 + 経路復元.
 今何回目のアクションをしたか,今どの状態か
を状態にして最小コストをメモる.
DPなら最後から順番に処理すると辞書順最小を求めやすい.
各クエリに対してO(N^2 M).

コメント

コメントの投稿

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

トラックバック

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

Appendix

Recent Articles

ブログ内検索

Ads


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