Entries

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

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

コメント

コメントの投稿

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

トラックバック

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

UVa 12547 - RNA Secondary Structure (この記事を編集する[管理者用])

Source

An European Reginal contest to be decided, SWERC 2012 Online (2012-11-24)
UVa 12547

問題概要

A,C,G,Uのみからなる文字列が与えられる.
ランレングスで圧縮されて与えられる.
AとU,CとGを線で結んでペアを作りたい.線は交差してはいけない.
また,CとGのペアを作れる最大数(20以下)が与えられる.
最も多くのペアを作った時,何ペアできるかを求める問題.
ランレングスで,最初の要素(最初の同じ文字が続いているブロックの文字数)と最後の要素の大きさは5000以下.
最初と最後を除いた部分の文字数は50文字以下.

解法

最初の要素と最後の要素をペアにできるなら,それをペアにしても他を妨害しないので,ペアを作っておく.
最初に続く文字列の数と,それがペアになれる文字の数を比較して,最初の文字がペアになれないなら消しておく.
などの処理をすれば,文字列の長さは150以下ぐらいにはなる.(もっと短くできるはず)
後は愚直にDPすれば良い.
部分文字列が与えられた時,最初にペアを作る要素の一番左の文字で場合分けして,そのペアになる文字の位置で場合分けして,C,Gのペアが何個作れるかをそれぞれに振り分ける.
一番左の文字を使わない場合は,一つサイズの小さい部分文字列に帰着されるので,そこは全部試したりしない.
O(長さ^3 * 20^2)ぐらいになるが,定数がかなり小さく通る.

コメント

コメントの投稿

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

トラックバック

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

Appendix

Recent Articles

ブログ内検索

Ads


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