Description：

给定一个序列 $A$ ，把序列保持原顺序的分成两个子序列，最小化代价之和，每个点的代价是它和它前面所有值得最大值减去这个值。

$1\leqslant n\leqslant 10^5$

Solution：

首先不难有一个 $O(n^3)$ 的做法，就是设 $f[i][j][k]$ 表示到了 $i$ ，第一个序列最大值为 $j$ ，第二个序列最大值为 $k$ 的最小值，考虑怎么优化他，由于 $j$ 或 $k$ 中一定有一个是前缀最大值，那么我们就可以只在状态里记录另外一个的值，然后考虑转移：

如果 $a[i]=mx[i]$ ，那么显然一定会更新最大值，那么我们不如保留比较小的那个更优，即 $f[i][j]=f[i-1][j]$ 。

否则的话，还要在分情况讨论：

如果 $j\geqslant a[i]$ ，那么加入它不改变状态，于是肯定放到代价小的队列里： $f[i][j]=f[i-1][j]+j-a[i]$ 。

否则的话，放到哪里都有可能，转移为： $$ f[i][j]=f[i-1][j]+mx[i]-a[i],f[i][a[i]]=\min(f[i-1][j](j<a[i])) $$ 这样的复杂度是 $O(n^2)$ 。