1.一般性动态规划
求第 $i$ 个状态时,可以用第$i-1$个状态表达或者$k$ 个第 $i$ 个状态以下的状态表达。
状态的设立要凭个人经验。
例题 : 钢条切割
题意:有 $1$ 根钢条,长度为 $n$ ,你可以将该钢丝分成很多份。
设 $i\in[1,n]$ , $d_i$ 表示长度为 $i$ 时,可以买出的价钱
求该钢条可以卖出的最大价钱。
考虑 $dp$ , 设 $f_i$ 表示一根长度为 $i$ 的钢条(可以分割)可以买出的最大价钱。
那么状态转移方程为:
$$f_i = \max_{k=1}^{i-1} f_k+f_{i-k}$$
那么本题即解决。
2. 背包
例题:
设 $dp_{i,j}$ 表示选择前 $i$ 个数且容量(此处即为采药时间)为 $j$ 时最多可以采集草药的价值, $w_i,val_i$ 分别表示第 $i$ 个草药所要花费的时间及应得的价值。
那么状态转移
2021-08-04 18:07:49
7KB
HTML
1