注意到 \(N \times M \le 2\times 10^7\)，因此不难得到一个 dp 做法。设 \(f_i\) 表示把前 \(i\) 个橙子装进箱子内的最小成本，则不难得到以下转移式：
\[f_i=\min_{i-j\le m,0 \le j < i} f_j+k+ ( i - j ) \times ( \max_{j < k \le i} a_k - \min_{j < k \le i} a_k )
\]
同时注意到最大最小值可以在倒着枚举 \(j\) 的时候顺便求出来，因此也容易做到时间复杂度 \(O(NM)\)。
#include <iostream>
#include <cstdio>
#define ll long long
#define N 200010using namespace std;int n,m,k;
ll f[N],a[N],mx,mi;int main()
{cin >> n >> m >> k;for( int i = 1 ; i <= n ; i ++ )cin >> a[i];for( int i = 1 ; i <= n ; i ++ ){f[i] = f[i - 1] + k;mx = mi = a[i];for( int j = i - 1 ; j >= max( i - m , 0 ) ; j -- ){f[i] = min( f[i] , f[j] + k + ( i - j ) * ( mx - mi ) );mx = max( mx , a[j] ),mi = min( mi , a[j] );}// cout << f[i] << endl;}cout << f[n];return 0;
}