dp[k]表示把前k个分成若干组，这时候他后面都已经加上了，应该多加的数。 就是dp[k]=ans_k+x(组数)*sum_ans(k+1,n); dp[k]->dp[i] Ask（l，r）代表l到r的最大值减去最小值 用st搞出来 Ans_sum/sum_ans都代表前缀和 Cost（l,r）代表l到r的ask+sum。 方法一：数学推导 Dp[k]=ans_k+x(组数)*sum_ans(i+1,n)+x*sum_ans(k+1,i); Dp[i]=ans_i+ans_sum(i+1,n)*(x+1) =ans_k+ans_sum(k+1,i)*(x+1)+ask(k+1,i)+ans_sum(i+1,n)*(x+1) =dp[k]+ans_sum(k+1,i)+ask(k+1,i)+ans_sum(i+1,n) =dp[k]+cost(k+1,i)+ans_sum(i+1,n); 方法二： 瞪眼法 多加了cost（k+1,i） 更新后面+sum_ans（i+1，n）； dp[i]=dp[k]+sum_ans(i+1,n)+cost(k+1,i);  优化 n*logn 实际上就是在找min（dp[k]+cost(k+1,i)）+一个定值。 Cost非递减，dp要是再增，肯定不行 从i-1开始维护一个dp是递减的序列。 A了