y-y-d-s.github.io:我是一个oier

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$ 个草药所要花费的时间及应得的价值。 那么状态转移