根据题意我们发现对于每个$A_{i}$，与它绝对值最小的一定是前$i$个数排序后在它前面或后面的数。
这样的话，我们维护一个单调的序列，插入每天的营业额时计算其波动值即可。
最暴力的便是插入排序，复杂度$(N^2)$，不能忍受。。
我们应选择复杂度为$(NlogN)$的方法。
维护一个单调序列自然想到了 set(平衡树也可以，但是作者懒，想用 STL 水过去，逃……)，因为可能有多个相同的营业额，所以我选择了 multiset。
根据题意我们发现对于每个$A_{i}$，与它绝对值最小的一定是前$i$个数排序后在它前面或后面的数。
这样的话，我们维护一个单调的序列，插入每天的营业额时计算其波动值即可。
最暴力的便是插入排序，复杂度$(N^2)$，不能忍受。。
我们应选择复杂度为$(NlogN)$的方法。
维护一个单调序列自然想到了 set(平衡树也可以，但是作者懒，想用 STL 水过去，逃……)，因为可能有多个相同的营业额，所以我选择了 multiset。
我们根据题意，发现这是一个 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)$的算法啦。。
2 / 2