洛谷P2234 - 「HNOI2002」营业额统计

 题解 / 洛谷
被浏览

根据题意我们发现对于每个 $A_{i}$ ,与它绝对值最小的一定是前 $i$ 个数排序后在它前面或后面的数。

这样的话,我们维护一个单调的序列,插入每天的营业额时计算其波动值即可。

最暴力的便是插入排序,复杂度 $(N^2)$,不能忍受。。

我们应选择复杂度为 $(NlogN)$ 的方法。

维护一个单调序列自然想到了 set(平衡树也可以,但是作者想用 STL 水过去,雾),因为可能有多个相同的营业额,所以选择了 multiset。

洛谷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)$的算法啦。。