An european regional / ACM ICPC, Southwestern Europe Regional Contest (2013-11-23)
UVa 12678

色を混ぜ合わせると新しい色ができる，
　$C_A + C_B = C_C$
という形のルールが $R$ 個与えられる．
連続する色の列の，隣り合う $2$ つを上のルールを適応して $1$ つの色になるまで続けるというゲームが有る．
ただし，ルールに無い場合は，そのような $2$ 色を混ぜ合わせることはできない．
おそらく，任意の列に対して，どの順番でルールを適応しても最終的にできる色は一意に定まると仮定して良いと思われる．（もしくは $1$ 色のみできない場合も有り得る）

いくつかクエリが与えられる．
各クエリでは，$C$ 個の色の列が与えられる．
ただし，各要素は厳密に何色なのかはわからず，この色である確率がいくらという形で与えられる．
混ぜていって最終的に $1$ 色できるような色の列のうち，最も確率が大きい物を考える．
その列を用いて最後にできる色は何かを求める問題．
ただし，最終的に $1$ 色にできない列しかないならそれを指摘する．
$R \leq 100$
$C \leq 500$

区間DPする．
それぞれの区間において，この色ができるという最大の確率をメモする．
状態数が $O(C^2 R)$ で，計算量は $O(C^3 R)$ になる．（$O(C^3 R^2)$ などにすると多分まずい）