题解

#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]+=2*M;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]+2*M);
        }
    }
}
void Output(){
    printf("%d",f[N]-M);
}
int main(){
    Read();
    Solve();
    Output();
    return 0;
}