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)だと畳み込みの部分が分けられない。

Monge

\(f\) が劣モジュラ関数ならば \(g(L, R):=f(\{a_L, a_{L+1}, \ldots, a_R\})\) はMongeになる。例えば、
\(A_{i,j} = \max_{i \leq k \leq j} a_k\) は Monge(ARC067F)。\(f(S)=\min(B, \sum_{i \in S} a_i )\) (\(a_i, B\) は非負) も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(最適二分探索木)

整数の積の分割の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)。

二項係数・階乗をまとめる

$$dp[i][j] = \sum_{u < i, v < j, (u, v) \in E} dp[u][v] + \sum_{k > 0} dp[i][j+k](j+k)$$

\(\sum_{\sum i_k=N, i_k \in \mathbb{Z_{\geq 0
}}}D^{i_1}x^{a_1}D^{i_2}x^{a_2} \cdots D^{i_w}x^{a_w}
= \prod \frac{\left(a_{k+1}+\sum_{i=1}^{k-1}(a_i+1)\right)!}{\left(\sum_{i=1}^{k-1} (a_i+1)\right)!}\) を用いる(公式集)。

凸関数の和

\(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\) とする。\(\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