设\(f[i][j]\)表示前\(i\)个数被恰好分为\(j\)个单调区间的最小花费，有\(f[i][j]=\overset{i-1}{\underset{p=1}{\min}}(f[p][j-1]+\text{cost}[p+1][i])\)，其中\(\text{cost}[i][j]\)表示区间\([i,j]\)分成一个单调序列的最小花费。于是问题转化成了求\(\text{cost}\)；而由题意不难知道这就是上面一道题目（只不过我们还需要求单调下降的情况，这里有个trick，直接将原数列所有数取相反数再求单调上升即可，从答案集合的角度可以知道是正确的）
然而，我们不能在外界循环\(i,j\)，然后通过\(O((j-i+1)\log (j-i+1))\)的复杂度去算\(\text{cost}[i][j]\)，这样会超时的。我们只能想办法利用之前已经计算过的信息。假设当前计算的是单调上升。我们外层枚举\(i\)，然后跑一次左偏树合并，当内层跑到\(j\)的时候，假设我们已经计算好了\(\text{cost}[i][i]\)到\(\text{cost}[i][j-1]\)，那么对于\(\text{cost}[i][j]\)来说，我们只用记录最后一段区间的贡献（这个需要记录左偏树的所有节点的权值和），再利用之前已经算好了的\(\text{cost}\)即可（子问题具有最优性）
需要注意的是，\(\text{cost}\)应该开三维，最后一维用来记录是单调上升还是单调下降，因为两者计算的时候不应该互相干扰，如果不再开一维的话，可以计算单调上升的时候会用到单调下降的\(\text{cost}\)，这样肯定就错了
具体见打卡代码
标签：text,cost,计算,上升,单调,左偏 From： https://www.cnblogs.com/dingxingdi/p/18367157