AT_dp

· · 题解

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，求最长路。

若有一条边 $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} 即可。