dp[i]=\min(dp[i],dp[j-1]+k+(mmax-mmin)\times(i-j+1))
$i-j+1$ 即为当前的数量。
## Code
这是我的第一篇题解，我希望它更加完美，经过优化，可以达到 27ms（看电脑配置）。
```cpp
#include<stdio.h> //比用万能头快
using namespace std;
long long n,m,k;
long long a[20005],dp[20005];
int main()
{
scanf("%lld%lld%lld",&n,&m,&k); //比 cin 快
for(int i=1;i<=n;i++) scanf("%lld",&a[i]);
for(int i=1;i<=n;i++)
{
long long biggest=a[i];
long long smallest=a[i];
dp[i]=2e14;
for(int j=i;j>=1&&i-j+1<=m;j--)
{
if(biggest<a[j]) biggest=a[j]; //比直接调 max 快很多
if(smallest>a[j]) smallest=a[j]; //比直接调 min 快很多
long long addition=k+(i-j+1)*(biggest-smallest);
if(dp[j-1]+addition<dp[i]) dp[i]=dp[j-1]+addition; //状态转移
}
}
printf("%lld",dp[n]); //比 cout 快
return 0;
}
```
[AC记录 28ms](https://www.luogu.com.cn/record/211564685)