Latin America - Brazil Sub Regional（20150913）
UVa 12960
$N$ 文字のアルファベット大文字のみからなる文字列 $S$ が与えられる．
また，$S$ の中でいくつか $0$ 個以上 $N$ 個以下の場所が指定されている．
$S$ の部分列（部分文字列ではない）で回文となるもののうち，指定された場所の文字が最も多く含まれるもののうち，最もの長いものの長さを求める問題．
動的計画法で $S$ の各部分文字列に対して，その部分文字列から作られる部分列で，指定された場所の文字が最も多く含まれるもののうち，もっとの長いものの（含まれる指定された場所の数，長さ）を計算していけば良い．
時間計算量は各テストケースに対して $O(N^2)$．
この部分を表示するには表示権限を持つユーザーでログインする必要があります．
Current time: 2024年04月26日06時18分09秒
Last modified: 2015年09月24日14時51分52秒 (by laycrs)
Tags: Competitive_Programming UVa_Online_Judge UVa_Contest_20150913_1
トップページに戻る
Logged in as: unknown user (not login)