UVa 13029 - Emoticons

Source

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

問題概要

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

• テストケースの数 $T$ は $T \leq 5000$ を満たす
• $N \leq 100000\ (10^5)$
• 全てのテストケースを通じての $N$ の和は $2100000\ (2.1 \times 10^6)$ を超えない

解法

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

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

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

Current time: 2024年04月26日07時29分57秒
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)