题解

#include<cstdio>
#include<algorithm>
#include<cstring>
const int maxn=2500+1;
int sum[maxn],f[maxn];
int N,M;
void Read(){
scanf("%d%d",&N,&M);
for(int i=1;i<=N;i++){
f[i]+=2M;int temp=0;
scanf("%d",&temp);
sum[i]=sum[i-1]+temp;
}
}
void Solve(){
for(int i=1;i<=N;i++){
f[i]+=sum[i];
for(int j=1;j<i;j++){
f[i]=std::min(f[i],f[j]+sum[i-j]+2M);
}
}
}
void Output(){
printf("%d",f[N]-M);
}
int main(){
Read();
Solve();
Output();
return 0;
}