题意
有 \(n\) 个数 , 每次可以合并相邻两个数为一个数 , 新的数的值是原来两个数的和 .
求最小操作次数 , 使得序列变为不降序列 .
\(case 1: n \le 3000\)
\(case 2: n \le 1e5\)
题解
做法一
一本通上给到的一种做法 .
首先设计状态 \(f_{i,j}\) 当前位置 \(i\) , 上一次转移位置 \(j\) , 存最小操作次数 . 直接更新 :
\[f_{i,j}=\max f_{j,k} \]其中要满足 \(i\) 到 \(j+1\) 的和不小于 \(k+1\) 到 \(j\) 的 .
显然所有可以取的 \(k\) 是一个后缀 , 因此直接记录后缀 \(\max\) , 就可以实现 \(O(1)\) 单次转移 . 可以用二分找到 \(k\) 的位置 .
不过 , 因为在 \(j\) 增大的过程中 , \(k\) 的位置相应地不减 , 所以可以用指针扫一遍 ,总复杂度 $O(n^2) $.
做法二
从刚才的做法可以得到一个观察 , 即在 \(j\) 尽量大且满足有方案的时候 , 由 \(j\) 向后贡献总是最优的.
具体地 :
对于有方案的所有 \(f_{i,j}\) , 最大的 \(j\) 向后更新的次数总比前面的多 . 这一点可以由刚才的单调性证明 .
因为最少操作次数相当于更多的转移次数 , 通过归纳法可以发现最大的 \(j\) 总有最小的操作次数 .
这一点其实可以直接观察得到 . 这样就得到了一个很强的 , 贪心性质的结论 .
这启发我们通过 dp 只计算到每一个位置最大的末尾数字 , 每次更新尽量取最大的 \(j\) , 满足 \(\sum^{i}_{k=j+1} \le f_j\) .
可以通过平衡树或线段树维护贪心过程 , 复杂度 \(O(n\log n)\) .
总结
题目本身并不难 . 找性质的过程还是很容易的 , 不管是通过观察直接 dp 的更新过程 , 还是直接模拟过程找规律 , 都能体会到一种很强的 **" 单调性结论 " ** .
具有单调性的问题常常可以从单调的角度 , 之抓住对结果最有用的部分 , 优化掉没有必要考虑的部分 , 比如单调栈 , 单调队列 . 更广义地看 , 例如在笛卡尔树上 , 这种方法在贪心 , 以及找性质都有一种体现 . 找性质时明确自己的目的 , 也许对于快速发现性质是有用的 .
标签：高手,le,题目,可以,位置,一本,次数,单调,贪心 From： https://www.cnblogs.com/youlv/p/18584224