T3 划分

$n\le 200$ 是给 $n^3$ DP的，直接将状态设为到 $i$ 为止的划分最大值，暴力枚举转移点并且直接扫过去计算贡献就好。

$n\le 5000$ 也就是对于同一个右端点，左端点从右往左的过程中维护一下区间的最小高度所在位置就可以 $O(n^2)$ 了。

$a_i$ 升序的话，就是每个区间取左端点的值，那么就是 $b_1$ 必取，然后剩下的价值 $b$ 想拿就拿，那么就把正的全拿了就行。

对于正解：

考虑普通的动态规划，定义 $F(i)$ 为 $1−i$ 的最大值，转移非常显然时间复杂度是 $O(n ^2)$ 很显然过不了。考虑使用数据结构优化 DP。

发现会影响转移的一定是比 $h(i)$ 要小的元素，考虑使用单调栈维护。

但是这样会产生一个问题，我们在 pop 的时候可能会把一些重要的信息忽略掉，这是不利于转移的，考虑在新开一个数组 $mx(i)$ 记录一下，表示元素 $i$ pop 掉单调栈里面的元素的 $mx$ 的最大值，为啥要这么做呢？

对于样例 2：

5
1 4 3 2 5
-3 4 -10 2 7

此时的 $F=\{ 0,−3,1,−3,0,0 \}$ 。

在对 $i=4$ 进行运算的时候，单调栈内的元素是 ${1,3}$(下标标号) 但是元素 $3$ 曾经将 $2$ pop 过，而此时如果直接用 $F$ 进行转移得到的是 $−3+2=−1$，因为我们忽略掉了 $2$ 所造成的贡献，因此要记录。

简而言之就是保存下其他的转移可能，并且只留存在把它弹出的地方即可。