看着没思路就推性质呗。
如果一段数不是严格单调就可以弄成两半使得差的和至少不减小。具体方法如下：
- 最大值与最小值有一个不在两端。直接将不存在最大值与最小值的一段割掉。因为一段的值为非负数所以差的和不会减少。
- 最大值与最小值均在两端。从前往后或者从后往前找到第一个不满足单调性的位置割开，最坏情况下差的和也会增加割的位置相邻两数之差。
现在要解决的问题就是端点上的数归入哪一边，DP 一下就好了。
CF484D Kindergarten
发布时间 2023-10-17 19:56:10作者: 御坂夏铃