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