前言
还是别把 \(\rm{POJ}\) 的题都水过去, 好好想一想
不是哥们, 紫题?
思路
还是先想朴素的 \(\rm{dp}\) , 令 \(f_i\) 表示拆分到了位置 \(i\), 此时的最大整数之和的最小值
\[f_i = \min_{k = 1}^{\sum_{j = k + 1}^{i} {a_j} \leq M}\{ f_k + \max_{j = k + 1}^{i} {a_j} \} \]这样 \(\mathcal{O} (n^2)\) , 怎么优化
考虑直接扔进 得塔斯抓克车儿 里面维护
事实上唯一的困难是我们需要动态地维护以 \(i\) 为结尾的 \(a\) 的后缀 \(\max\)
我们可以发现, 在之前的基础上添加 \(a_i\) , 我们段树二分找到第一个地方 \(p\) 使得其之后的后缀 \(\max\) \(\leq a_i\) , 那么我们就需要对 \([p, i]\) 的后缀 \(\max\) 值修改为 \(a_i\) , 解决了这个问题, 我们只需要考虑 \(\rm{dp}\) 的维护, 新开一棵线段树维护即可
复杂度 \(\mathcal{O} (n \log n)\)
实现
不太好写, 先不写了, 只是码量的堆罢了
总结
后缀 \(\max\) 的动态维护常用技巧:
- 线段树
- 单调栈 + 二分 / 并查集