根据另一篇题解，结合课上学习的内容，不难发现可以进行最值优化，每一次循环其实就多了一个j=i-1的情况，用之前的val更新val即可

时间复杂度O(n)

觉得好就点个赞吧！

#include<bits/stdc++.h>
using namespace std;
int n,k,d,a[1005],val;
int main(){
    cin>>n>>k>>d;
    for(int i=1;i<=n;i++) cin>>a[i];
    val=a[1];
    for(int i=2;i<=n;i++){
        val=min(val,val+(a[i]-a[i-1])*k-d);
    }
    cout<<val;
}

根据题意，设f[i]表示解决完第i个学生的问题后，花费的最少精力，则

$f[i]=f[j]+(a[i]-a[j])*k-d (1<=j<i)$

直接$O(n^2)$dp即可。

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N=1000005;
ll a[N],n,m,k,s,t,d,f[N];
int main(){
	cin>>n>>k>>d;
	for (int i=1;i<=n;++i) cin>>a[i];
	f[1]=a[1];
	for (int i=2;i<=n;++i)
		for (int j=1;j<i;++j)
			f[i]=min(f[i],f[j]+(a[i]-a[j])*k-d);
	cout<<f[n];
}