AtCoder DP系列刷题记录
直面自己的弱点。
A Frog 1
简单线性 \(\text{dp}\)，令 \(dp_i\) 为跳到第 \(i\) 块石头的最小花费，易得：
\[dp_i+=\min(|a_i-a_{i-1}|,|a_i-a_{i-2}|)
\]
B Frog 2
很快就写完了，但是一直调了十分钟，耻辱啊。
如果反着跳，第 \(i\) 根木桩只能从第 \(i+1\) 或 \(i+2\) 木桩上跳到，则有：
\[dp_i=\min(dp_{i+1}+|a_i-a_{i+1}|,dp_{i+2}+|a_i-a_{i+2}|)
\]
C Vacation
语文课花两分钟想出来的。
显然对于 \(a_i\)，它只能接受 \(b_{i-1}\) 和 \(c_{i-1}\) 的转移，其他两边情况相同，则有：
\[dp_{i,0}=\max(dp_{i-1,1},dp_{i-1,2})+a_i
\]
\[dp_{i,1}=\max(dp_{i-1,0},dp_{i-1,2})+b_i
\]
\[dp_{i,2}=\max(dp_{i-1,0},dp_{i-1,1})+c_i
\]
D Knapsack 1
\(01\) 背包板子，不讲了。
E Knapsack 2
与 \(01\) 背包基本一致，但数据范围大了很多，将 \(\text{dp}\) 数组表示的东西换一下就行了，不表示价值，表示重量。像 \(01\) 背包一样压维，则有：
\[dp_j=\min(dp_j,dp_{j-v_i}+w_i)
\]