Skip to content →

DP まとめ

考察からまとめ中………

\(a[i] = g[i] \oplus \bigoplus_{j=s[i]}^{t[i]} b[j]\)
b[j] は a[1:j] から計算された元、\(\oplus\) はモノイドの演算。セグメント木に載せる。定数個連ねた\(a[i] = g[i] \oplus \bigoplus_k\bigoplus_{j=s_k[i]}^{t_k[i]} b_k[j]\) のような形もある。
項の依存関係(DAG)より、単位元(min の場合はINF)で初期化しておくとサボれる条件は無視する。例えば下の例では min の範囲の条件である \(j < i\) は考察するときは無視してよい。
\begin{align}
a[i] &= \min_{g[j] < g[i], j < i}(a[j] + f_1[i] + f_2[j]) \\
&= f_1[i]+\min_{g[j] < g[i]}b[j]
\end{align}
区間和の場合は O(1)
\begin{align}
a[i] &= \sum_{j=s[i]}^{t[i]} a[j] \\
&= b[t[i]]-b[s[i]-1]
\end{align}

区間DP

\begin{align}
a[l][r] &= \sum_{\substack{l < s < r,\\ g[l] < g[s] < g[r]}} \left(a[l][s] + a[s][r]\right)\\
&= \sum_{g[l] < g[s] < g[r]} a[l][s] + \sum_{g[l] < g[s] < g[r]} a[s][r]\\
&= \sum_{g[l] < g[s] < g[r]} b_l[s] + \sum_{g[l] < g[s] < g[r]} c_r[s]\\
\end{align}

min だと畳み込みの部分が分けられない。

Published in データ構造

Comments

コメントを残す

メールアドレスが公開されることはありません。

CAPTCHA