关于第二题： 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