AtCoder DP Practice

标签：AtCoder min Practice DP 线性 转移 dp

众所周知，AtCoder 有一场极 educational 的 DP Contest。

A

裸的线性 DP，设 \(dp_i\) 表示跳到第 \(i\) 个格子的最小费用，显然有转移：

\[dp_{i} = \min(dp_{i - 1} + |h_i - h_{i - 1}|, dp_{i - 2} + |h_i - h_{i - 2}|) \]

边界为 \(dp_1 = 0, dp_2 = |h_2 - h_1|\)。

B

裸的线性 DP，设 \(dp_i\) 表示跳到第 \(i\) 个格子的最小费用，显然有转移：

\[dp_{i} = \min_{1 \leq j \lt i} dp_j + |h_i - h_j| \]

边界为 \(dp_1 = 0\)。

C

裸的线性 DP，设 \(f_{i, 0}, f_{i, 1}, f_{i, 2}\) 分别为第 \(i\) 天选择 \(a, b, c\) 活动的最大值，显然有转移：

\[\begin{cases} f_{i, 0} = \min(f_{i - 1, 1}, f_{i - 1, 2}) + a_i \\ f_{i, 1} = \min(f_{i - 1, 0}, f_{i - 1, 2}) + b_i \\ f_{i, 2} = \min(f_{i - 1, 0}, f_{i - 1, 1}) + c_i \\ \end{cases} \]

边界在转移中已经处理。

答案为 \(\min(f_{n, 0}, f_{n, 1}, f_{n, 2})\)。

标签：AtCoder,min,Practice,DP,线性,转移,dp
From： https://www.cnblogs.com/xsyc/p/18613266