滚动数组
#include<stdio.h>
#include<iostream>
#include<string.h>
#include<algorithm>
#include<queue>
#include<stack>
#include<map>
#include<string>
#include<stdlib.h>
#define INF_MAX 0xfffffff
#define INF 999999
#define max3(a,b,c) (max(a,b)>c?max(a,b):c)
#define min3(a,b,c) (min(a,b)<c?min(a,b):c)
#define mem(a,b) memset(a,b,sizeof(a))
using namespace std;
struct node
{int u;int v;int w;bool friend operator < (node a, node b){return a.w < b.w;}
}edge[1001];
int gcd(int n,int m){if(n<m) swap(n,m);return n%m==0?m:gcd(m,n%m);}
int lcm(int n,int m){if(n<m) swap(n,m);return n/gcd(n,m)*m;}
int n,l;
int ds;
void find(int i,int &ls,int &rs)
{if(i<n-1){ls=ds*i;if((l-((ds+1)*(n-1-i)))>ls){ls=(l-((ds+1)*(n-1-i)));}rs=l-(ds*(n-1-i));if((ds+1)!=-1&&((ds+1)*(i))<rs){rs=((ds+1)*(i));}}else{ls=rs=l;}
}
int main()
{int i,j,d[100001];scanf("%d%d",&n,&l);for(i=0;i<n;i++){scanf("%d",&d[i]);}if(n==1){printf("0\n");return 0;}int sum;ds=l/(n-1);sum=0;if(l%(n-1)==0){sum+=d[0]-0;for(i=1;i<n;i++){sum+=abs(d[i]-i*ds);}printf("%d\n",sum);}else{int dp[2][200001];for(i=0;i<2;i++){for(j=0;j<=l;j++)dp[i][j]=INF_MAX/2;}dp[0][0]=d[0];for(i=1;i<=n-1;i++){int ls,rs;find(i,ls,rs);for(j=ls;j<=rs;j++){dp[i%2][j]=dp[(i-1)%2][j-ds]+abs(d[i]-j);if(j-ds-1>=0)dp[i%2][j]=min(dp[i%2][j],dp[(i-1)%2][j-ds-1]+abs(d[i]-j));}if(i>3){int l1,r1;find(i-2,l1,r1);for(j=l1;j<=r1;j++){if(j<ls||j>rs){dp[i%2][j]=INF_MAX;}}}}printf("%d\n",dp[(n-1)%2][l]);}return 0;
}