官方,网上题解似乎都是$O(nlogn)$的

前面应该都差不多:

$dp[i]$表示$1..i$的$min$

则$dp[i]=min(dp[j-1]+max(h[j..i]))$ 且$w(j)+..w(i)<=L$

从左到右枚举$i$，

则所有$j$被所有$h[k]=max(h[k..i])$的$k$分成一段一段

每段由于$dp[j]$的单调递增肯定取最左边的那个$j$

$k$可以用单调栈维护

由于$w(j)+..w(i)$的限制，可以的$j$的左边界是单调左移的

所以问题就变成了两端删除，一端插入，维护最值。

我想了一个$O(n)$的方法，而且是能解决两端插入的 (求问有没有别的方法)

就是左右各开一个栈维护最值，

左边删除插入就用左边的

右边删除插入就用右边的

如果左或右的栈删没了，就重构，把队列分成两半，左边分一半，右边分一半

每次重构的时间复杂度和下次删完所需的时间是一样的，所以复杂度是线性的。

卡常后拿了bzoj rank1