Entries

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

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

コメント

コメントの投稿

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

トラックバック

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

LiveArchive 4961 - Assembly line (この記事を編集する[管理者用])

Source

Europe - Southwestern (Madrid, Spain) - 2010/2011
UVa: SWERC Contest (2010-11-27) (blog)
LiveArchive 4961

問題概要

200文字以下のアルファベット小文字からなる文字列Xが与えられる.
隣り合う2文字を別の文字に置き換えるコストが与えられる.
(任意の2文字に対して1つの規則が与えられ,置き換わる文字とコストが指定される)
Xを1文字にするまでに必要なコストと,最終的な文字を求める問題.
コスト最小の最終的な文字の候補がいくつもあるなら,与えられた順番で一番早いのを返す.

解法

どの区間をどの1文字にするのに必要な最小コストをメモしてDPする.

コメント

コメントの投稿

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

トラックバック

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

Appendix

Recent Articles

ブログ内検索

Ads


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