Entries

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

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

コメント

コメントの投稿

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

トラックバック

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

Aizu 2090 - Repeated Subsequences (この記事を編集する[管理者用])

Source

ICPC OB/OGの会 夏合宿 2007: 2日目
Aizu 2090

問題概要

300文字以下の文字列が与えられるので,それを適当な場所で2つに分けて,その2つの文字列の最長部分列(最長部分文字列ではない)のうち,最も長いものを求める問題.
答えが複数あるならどれでも良いので1つ求める.

解法

普通に全ての分け方に対してDPで最長部分列を求める.分け方がO(n),DPがO(n^2)で,合計で計算時間量O(n^3).
あおいちゃんに褒められたくて,少し枝刈りしてみたのだけど,コードの短さ順で1位/1人とか悲しいこと言われただけだったよ,しくしくorz
(同じコードをC++として送っても,短さ順で2位/6人とか言われただけだったよorz)
枝刈りは,
 str.substr(0,a) と str.substr(a)
の最長部分列を求めるついでに
 str.substr(0,a+1) と str.substr(a)
の最長部分列の長さも計算してみて,同じなら
 str.substr(0,a+1) と str.substr(a+1)
を求める処理は飛ばしても良いよね,とかそういう感じのとか.

コメント

コメントの投稿

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

トラックバック

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

Appendix

Recent Articles

ブログ内検索

Ads


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