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 の範囲の条件 \(j < i\) は全ての項を \(\infty\) で初期化することにより無視できる。
\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

区間dpは区間の小さい順に更新していく。2次元平面に図示すると更新順序は下のようになる。 

足し算の畳み込み

\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}
BITを使うと \(O(n^2 \log n)\) になる(ARC108E)。分配法則が成り立たない演算(例えばminや掛け算)だと畳み込みの部分が分けられない。

min plus の畳み込み (Monge)

\(w_{i, j}\) が Monge かつ 単調非減少関数 (\([i, j] \subset [k, l]\) ならば \(w_{i, j} \leq w_{k, l}\)) のとき $$dp[i][j]=\min_{i < s < j}(dp[i][s]+dp[s][j]) + w_{i,j}$$ は Mongeで \(O(n^2)\) になる(ref)。

\(a \leq b\) とする。f が区間上のMongeのとき、優モジュラと同様にして、区間が大きいほど、f の微分も大きくなる。ここから dp がMongeになる。従って、\(g(a, b) = \mathrm{argmin}_s ( f(a, s) + f(s, b))\) と置くと \(g(a, b-1) \leq g(a, b) \leq g(a+1, b)\).  すると、$$g(0, d-1) \leq g(0, d) \leq g(1, d) \leq g(1, d+1) \leq g(2,d+1)\leq g(2, d+2) \leq \cdots$$となるので\(O(n^2)\) となる。

Monge

\(f\) が集合上の優モジュラ関数ならば \(g(L, R):=f([L, R])\) はMongeになる。例えば、
\(A_{i,j} = \min_{i \leq k \leq j} a_k\) は Monge(ARC067F)。優モジュラ関数の定義
\begin{align}
&\forall S, \forall T, f(S \cap T) + f(S \cup T) \geq f(S) + f(T) \\
\Leftrightarrow & \forall A, \forall c, \forall d, f(A \cup c \cup d) – f(A \cup c) \geq f(A\cup d) – f(A)
\end{align}
より \(f\) (負も取る)は集合が大きいほど加速的に大きくなる。

整数の積の分割のDP

整数から半環への写像 \(g\) について、積の分割の和を取って $$f(n, k) = \sum_{\prod \lambda_i = n, \lambda_i \leq \lambda_{i+1}, \lambda_i \leq k} \prod_{i} g(\lambda_i)$$ と置くと、$$f(n, k) = f(n,k-1)+g(k)f(n/k,k)$$ が成り立つ。\(n, k \leq N\) について \(O(N \log N)\) で列挙できる(CF1699E)。

凸関数の和

\(x_1 \leq x_2 \leq \cdots \leq x_n\) の下、\(\min \sum f_i(x_i)\) を求めよ。ただし、\(f_i(x)\) は凸関数である(yuki2009)。\(f_i(x)\) が最小となる \(x\) を \(\omega_i\) とする。\(\frac{d}{dx} f_i,\frac{d}{dx} f_j \) の符号が互いに相異なるのは、区間 \([\omega_i, \omega_j]\) (\(\omega_i < \omega_j\)) だけである。\(\omega_{i} > \omega_{i+1}\) ならば、\(x_i = x_{i+1}\) としてもよい。凸関数の和は凸関数であるから、\(n\)が一つ小さい問題に帰着できた。\(\omega_1 \leq \omega_{2} \leq \cdots \leq \omega_n\) ならば \(x_i = \omega_i\) とするのが最適。

Published in データ構造

Comments

コメントを残す

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

CAPTCHA