本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2025-10-14 17:04:49

A/B

题目

A是B中k=2的特殊情况。

设 $f_i$ 表示跳到第 $i$ 个台阶的最小代价。

首先，在第 $i$ 个台阶我们可以从 $i-1,i-2,....,i-k$ 转移过来。

不难列出转移方程

$$f_i=\min_{j=\max(1,i-k)}^{i} f_j+|h_i-h_j|$$

$dp_1=0$

C

不难想到状态，设 $f_{i,1/2/3}$ 表示第 $i$ 天选择第 $1/2/3$ 种活动可获得的最大总幸福度。

很好转移。

$$f_{i,1}=a_i+\max(f_{i-1,2},f_{i-1,3})$$ $$f_{i,2}=b_i+\max(f_{i-1,1},f_{i-1,3})$$ $$f_{i,3}=c_i+\max(f_{i-1,2},f_{i-1,1})$$

答案即为 $\max(f_{n,1/2/3})$

D

简单背包

设 $f_i$ 表示背包容量为 $i$ 的时候最大价值。

转移 $$f_j=\max(f_j,f_{j-w_i}+v_i)$$

输出 $f_m$ 即可。

E

最大范围为 $10^9$，D的状态不再适合此题。

可以将价值和重量交换

设 $f_i$ 表示取价值为 $i$ 的物品的最小重量。

不难转移 $$f_j=\max(f_j,f_{j-v_i}+w_i)$$

答案只需要统计最大的价值使得其重量符合题目要求即可。

F

最长公共子序列。

设 $f_{i,j}$ 为 $s$ 的前 $i$ 项与 $t$ 的前 $j$ 项的LCS长度。

若 $s_i=t_j$，则 $f_{i,j}=f_{i-1,j-1}+1$

否则，则 $f_{i,j}=\max(f_{i-1,j},f_{i,j-1})$

输出 $f_{s.size(),t.size()}$

G

给定一个dag，求最长路。

$f_i$ 表示遍历到第 $i$ 个点的最长路。

若有一条边 $j \to i$，那么 $f_i=\max(f_i,f_j+1)$

dfs即可。

H

设 $f_{i,j}$ 表示走到 $(i,j)$ 这个点。

类似金字塔转移即可。

I

设 $f_{i,j}$ 表示到第 $i$ 个硬币有 $j$ 个向上的概率。

不难转移 $$f_{i,j}=f_{i-1,j-1} \times p_i +f_{i-1,j} \times (1-p_i)$$

输出 $\sum_{j>n-j} f_{n,j}$ 即可。