UVa 13029 - Emoticons

Source

An Asian Preliminary Regional(20151205)
(ICPC Dhaka 2015 Preliminary)
UVa 13029

問題概要

$\verb|^|$ と $\verb|_|$ のみからなる長さ $N$ の文字列 $S$ が与えられる.
同じ部分を使わない部分列(連続な部分列でなくて良い)として,$\verb|^_^|$ が最大で何個作れるかを求める問題.

解法

左からなぞっていき,現在部分列として,$\verb|^|$,$\verb|^_|$,$\verb|^_^|$,$\verb|^_^_|$ を何個作れているかを計算していく.
つまり,次の文字が $\verb|_|$ なら,$\verb|^_^|$ があるなら $\verb|^_^_|$ に変え,そうでなく $\verb|^|$ があるなら $\verb|^_|$ に変える.
次の文字が $\verb|^|$ なら,$\verb|^_^_|$ があるなら $\verb|^_|$ と $\verb|^_^|$ に変え,そうでなく $\verb|^_|$ があるなら $\verb|^_^|$ に変え,そうでないなら $\verb|^|$ を作る.
そうやって,最終的にできた $\verb|^_^|$ と $\verb|^_^_|$ の数の合計が答えとなる.

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

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


Current time: 2017年07月23日17時41分56秒
Last modified: 2015年12月16日01時06分47秒 (by laycrs)
Tags: Competitive_Programming UVa_Online_Judge UVa_Contest_20151205_1
トップページに戻る

Logged in as: unknown user (not login)

ログイン: