洛谷P1107 - 雷涛的小猫

被浏览

我们根据题意,发现这是一个 DP 题,定义$f_{i,j}$表示在高度为$i$,当前要爬的树为$j$所能获得的最大柿子数。

易得状态转移方程:$f_{i,j}=max(f_{i-1,j},f_{i-delta,k}) (1\leq k \leq n)$ 当$i>delta$时后一项成立。

于是我们得到了一个时间复杂度为$O(H \times N^2)$,空间复杂度为$O(N \times H)$的算法啦。。