UVa 12960 - Palindrome

Source

Latin America - Brazil Sub Regional(20150913)
UVa 12960

問題概要

$N$ 文字のアルファベット大文字のみからなる文字列 $S$ が与えられる.
また,$S$ の中でいくつか $0$ 個以上 $N$ 個以下の場所が指定されている.
$S$ の部分列(部分文字列ではない)で回文となるもののうち,指定された場所の文字が最も多く含まれるもののうち,最もの長いものの長さを求める問題.

解法

動的計画法で $S$ の各部分文字列に対して,その部分文字列から作られる部分列で,指定された場所の文字が最も多く含まれるもののうち,もっとの長いものの(含まれる指定された場所の数,長さ)を計算していけば良い.
時間計算量は各テストケースに対して $O(N^2)$.

C++によるスパゲッティなソースコード

この部分を表示するには表示権限を持つユーザーでログインする必要があります.


Current time: 2017年11月22日00時49分20秒
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)

ログイン: