不难想到线性DP

$f_i=\min\limits_{0\le j<i并且\sum_{k=j+1}^i A_k\le m}\{f_j+\max\limits_{j+1\le k\le i}\{A_j\}\}$

引理:

  • 在上述方程中,若$j(0\le j<i)$可能成为最优解,则除了$\sum_{k=j+1}^i A_j\le m$外,必然还满足一下两个条件之一:

    1. $$A_j=\max\limits_{j\le k\le i}\{A_k\}$$
    2. $\sum_{k=j}^i A_k>m$(即j是满足$\sum_{k=j+1}^i A_k\le m$的最小的$j$)\

证明:

  • 反证法。假设两个条件都不满足,即$A_j<\max\limits_{j\le k\le i}\{A_k\}$且$\sum_{k=j}^i A_k\le m$。由此可知$\max\limits_{j\le k\le i}\{A_k\}=\max\limits_{j+1\le k\le i}\{A_k\}$,由于$f_i$是单调的,因为多一个数出来,就有可能付出更大的代价。

即$f_{j-1}\le f_{j}$,那么$f_{j-1}+\max\limits_{j\le k\le i}\{A_k\}\le f_j+\max\limits_{j+1\le k\le i}\{A_k\}$,那么$j-1$优于$j$,即说明$j$不满足以上两个条件时,不可能成为最优解。

$t$为最小能满足$\sum_{k=t+1}^i a[i]<=m$ ,因此$j\in[l,r],t<q[j]$,都有$\sum_{k=q[j]+1}^i<=m$,那么需要满足另外一个条件$a[ql[j]]=\max\limits_{ql[j]\le k\le i}\{a[k]\}$,第一个条件是线性的,第二个条件用单调队列维护一下,但由于队列中每个值都有可能成为最优解,因此开棵平衡树维护一下。