Z - Frog 3 Editorial by rsk0315
有名な解法として、convex hull trick (CHT) を用いるものがありますが、それ以外の解法もあります。俗に LARSCH algorithm と呼ばれているものを使います。
状態 \(j\) から \(i\) への遷移コスト \(W(j, i)\) が concave QI と呼ばれる不等式を満たすとき、
\[ E[i] = F[j] + W(j, i) \text{ for } 0\le j<i<n \]
で表される DP を \(O(n)\) 時間で計算できます。ここで、\(E\) がいわゆる DP 配列で、\(F[i]\) は \(E[i]\) から高速に計算できる値(\(F[i] = E[i]\) でも ok)です。
concave QI とは?
2 変数関数 $W(\bullet, \bullet)$ が concave QI (quadrangle inequality) を満たすとは、任意の $i < i' < j < j'$ に対し、$W(i, j) + W(i', j') \le W(i, j') + W(i', j)$ を満たすことを言います。
+--------+ i | A B | | | i' | C D | +--------+ j j'上のような図のイメージで、
A + D <= B + C
となっています。
あるいは以下のような区間と見ることもできそうです。
i i' j j' |-----A-----| |-----D----| |--------B-------| |--C--|
逆向きの不等式は concave QI と呼ばれます。
この問題での遷移コスト \(W(j, i) = (h_j - h_i)^2+C\) も conave QI を満たすので、このアルゴリズムを使うことができます。
CHT の解法では \((h_j-h_i)^3+C\) や \((h_j-h_i)^4+C\) のようなコストを扱うのはつらそうですが、この解法では問題ありません。
todo: LARSCH algorithm 自体の解説を書く。
実装例:提出 #34087558(あまり洗練されていない)
参考:Larmore, Lawrence L., and Baruch Schieber. “On-line dynamic programming with applications to the prediction of RNA secondary structure.” Journal of Algorithms 12, no. 3 (1991): 490–515.
posted:
last update: