Entries

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

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

コメント

コメントの投稿

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

トラックバック

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

UVa 12473 - Common Palindrome (この記事を編集する[管理者用])

Source

First Bangladeshi Contest of 2012-2013 Season (2012-07-07)
UVa 12473

問題概要

60文字以下の文字列A, Bが与えられる.
A, Bの共通の部分列 (部分文字列ではない) の中で最長の回文の長さを求める問題.
文字はアルファベット小文字のみ.

解法

まず,それぞれのアルファベットに対して,それぞれの場所より右(左)で,最初に出てくる場所を計算しておく.
(制限時間が長いのでそこまでしなくても通る気がするが)
回文の最初の文字で場合分けすると,A,Bのある区間の中で最長の回文を探す問題に帰着されるのでDPできる.
状態数はO(60^4)で,計算量O(60^4 * 26)だけど,実際はそんなに調べないので遅くない.

コメント

コメントの投稿

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

トラックバック

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

Appendix

Recent Articles

ブログ内検索

Ads


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