ソースコード
//オレンジの出荷
#include<iostream>
#include<stdio.h>
#include<string>
#include<vector>
#include<map>
using namespace std;
int N,M;
long long K;
long long orange[20000] = {};
long long cost[20000][1000] = {};
long long cost_min[20000] = {};
long long c_cost(int A,int B){//AからB個
if(cost[A][B] != 0){
return cost[A][B];
}
else if(A+B > N){
cost[A][B] = -1;
return -1;
}
else{
long long min = 9223372036854775807;
long long max = -1;
for(int i=0; i<B; i++){
if(min>orange[A+i]) min=orange[A+i];
if(max<orange[A+i]) max=orange[A+i];
}
cost[A][B] = B*(max-min)+K;
return cost[A][B];
}
}
long long c_min(int A){//Aより大きいときの最小値
if(cost_min[A] != 0){
return cost_min[A];
}
else{
long long min = 9223372036854775807;
for (int i=1; i+A<=N && i<=M; i++){
long long tmp;
if(A+i==N){
tmp = c_cost(A,i);
}
else{
tmp = c_cost(A,i)+c_min(A+i);
}
if(min>tmp) min=tmp;
}
cost_min[A] = min;
return min;
}
}
int main(){
cin >> N >> M >> K;
for(int i=0; i<N; i++){
cin >> orange[i];
}
cout << c_min(0) << endl;
return 0;
}