关于第二题：

f[i]表示前i个分成若干组,后面的分成一组的最优解

设Range(l,r)=max(a[l..r])-min(a[l..r]);这是极差

设cost(l,r)=sum[r]-sum[l-1]+Range(l,r);一段区间和+极差

f[i]=min(f[k]+cost(k+1,i)+sum[n]-sum[i]) (k∈[0,k] and sum[i]-sum[k]<=W)
这样直接转移是O(n^2)的,下面考虑删除一些没用的决策k，类似单调队列的做法
(但不是队头最优),当然真正的大哥直接线段树维护了

将上述方程化简得

f[i]=min(f[k]-sum[k]+Range(k+1,i))+sum[n]   k∈[0,i]

仔细观察上方程，当i增加时
我们发现，k的取值下界可能会增大，因为sum[i]-sum[k]>W 时不符合条件
这样就可以排除一些没用的k。

此外对于一组数据，有Range(k+1,x)>=Range(i+1,x)  其中k<i  x>=i+1
因为Range表示的是一组数据的极差，这个结论是很显然的

下面我们来看看f[k]-sum[k]，当i增加时，k可以取到i了，那么
如果之前k<i的f[k]-sum[k]>=f[i]-sum[i]

由上述两个不等式
可得f[k]-sum[k]+Range(k+1,x)>=f[i]-sum[i]+Range(i+1,x) 其中x>=i+1
这个时候不如取k=i的时候优秀，所以应当抛弃

但f[k]-sum[k]<f[i]-sum[i]时就不知道了
我们无法利用不等式基本定理来得到
f[k]-sum[k]+Range(k+1,x)与f[i]-sum[i]+Range(i+1,x)的关系 其中x>=i+1
所以仍然需要枚举这些K值来看看哪个最小，
但是此时的K已经很少了，枚举起来很快


所以每次新增加一个i，就可以抛弃之前f[k]-sum[k]>=f[i]-sum[i]的无用k值
所以可以创建一个单调队列，这里面的k值满足f[k]-sum[k]单调递增
这样排除的时候就可以从右边一个个排除了
代码：https://ac.nowcoder.com/acm/contest/view-submission?submissionId=41588931