背景
但也有很多百姓平民想搭乘方舟，毕竟他们不想就这么离开世界，所以他们决定要么登上方舟，要么毁掉方舟。
LHX教主听说了这件事之后，果断扔掉了手中的船票。在地球即将毁灭的那一霎那，教主自制了一个小型火箭，奔向了月球……
教主登上月球之后才发现，他的女朋友忘记带到月球了，为此他哭了一个月。
但细心的教主立马想起了小学学过的一篇课文，叫做《嫦娥奔月》，于是教主决定，让嫦娥做自己的新任女友。
描述
见到嫦娥之后，教主用温柔而犀利的目光瞬间迷倒了嫦娥，但嫦娥也想考验一下教主。
嫦娥对教主说："看到那边的环形山了么？你从上面那个环走一圈我就答应你～"
教主用LHX卫星定位系统查看了环形山的地形，环形山上一共有N个可以识别的落脚点，以顺时针1~N编号。每个落脚点都有一个海拔，相邻的落脚点海拔不同（第1个和第N个相邻）。
教主可以选择从任意一个落脚点开始，顺时针或者逆时针走，每次走到一个相邻的落脚点，并且最后回到这个落脚点。
教主在任意时刻，都会有"上升"、"下降"两种状态的其中一种。
当教主从第i个落脚点，走到第j个落脚点的时候（i和j相邻）
j的海拔高于i的海拔：如果教主处于上升状态，教主需要耗费两段高度差的绝对值的体力；否则耗费高度差平方的体力。
j的海拔低于i的海拔：如果教主处于下降状态，教主需要耗费两段高度差的绝对值的体力；否则耗费高度差平方的体力。
当然，教主可以在到达一个落脚点的时候，选择切换自己的状态（上升→下降，下降→上升），每次切换需要耗费M点的体力。在起点的时候，教主可以自行选择状态并且不算切换状态，也就是说刚开始教主可以选择任意状态并且不耗费体力。
教主希望花费最少的体力，让嫦娥成为自己的女朋友。
输入格式
接下来一行包含空格隔开的N个正整数，表示了每个落脚点的高度，题目保证了相邻落脚点高度不相同。
输出格式
测试样例1
输入
输出
备注
从第3个落脚点开始以下降状态向前走，并在第4个落脚点时切换为上升状态。
这样共耗费4 +(7)+3+1+2^2+2^2+4=27点体力。
【数据规模】
对于10%的数据，N ≤ 10；
对于30%的数据，N ≤ 100，a[i] ≤ 1000；
对于50%的数据，N ≤ 1000，a[i] ≤ 100000；
对于100%的数据，N ≤ 10000，a[i] ≤ 1000000，M ≤ 1000000000；
先说说网上的随机化算法优化O(n^2)暴力——>α(nlogn){常数60+}
//非常有可能被卡常，且有可能卡WA
//期望得分：100
//实际得分：80-100
#include<ctime>
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<iostream>
#define pf(x) ((ll)(x)*(ll)(x))
#define OPT __attribute__((optimize("O2")))
using namespace std;
typedef long long ll;
const int N=;
ll f[N][],ans[N];
int n,m,a[N<<],b[N],tp[];
OPT inline int read(){
int x=,f=;char ch=getchar();
while(ch<''||ch>''){if(ch=='-')f=-;ch=getchar();}
while(ch>=''&&ch<=''){x=x*+ch-'';ch=getchar();}
return x*f;
}
OPT inline ll DP(int start){
if(ans[start]) return ans[start];
for(int cnt=,i=start;i<=start+n;i++) b[++cnt]=a[i];
f[][]=f[][]=;
for(int i=;i<=n+;i++){
if(b[i]>b[i-]){
f[i][]=min(f[i-][]+m+b[i]-b[i-],f[i-][]+b[i]-b[i-]);
f[i][]=min(f[i-][]+m+pf(b[i]-b[i-]),f[i-][]+pf(b[i]-b[i-]));
}
else{
f[i][]=min(f[i-][]+m+b[i-]-b[i],f[i-][]+b[i-]-b[i]);
f[i][]=min(f[i-][]+m+pf(b[i]-b[i-]),f[i-][]+pf(b[i]-b[i-]));
}
}
return ans[start]=min(f[n+][],f[n+][]);
}
OPT int main(){
srand(time());
n=read();m=read();
for(int i=;i<=n;i++) a[i+n]=a[i]=read();
for(int i=;i<=;i++) tp[i]=rand()%n+;
for(double T=n;T>=;T*=0.5){
for(int i=,now;i<=;i++){
for(int j=;j<=;j++){
now=tp[i]+sin((double)(rand()%)/)*T;
if(now<=||now>n) continue;
if(DP(now)>=DP(tp[i])) continue;
tp[i]=now;
}
}
}
ll Ans=0x7fffffffffffffffLL;
for(int i=;i<=;i++) Ans=min(Ans,ans[tp[i]]);
cout<<Ans;
return ;
}
正经算法
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#define pf(x) (1LL*(x)*(x))
using namespace std;
typedef long long ll;
inline int read(){
int x=,f=;char ch=getchar();
while(ch<''||ch>''){if(ch=='-')f=-;ch=getchar();}
while(ch>=''&&ch<=''){x=x*+ch-'';ch=getchar();}
return x*f;
}
const int N=;
int n,m,a[N<<];
ll f[N][][],Ans;
void DP(){
for(int i=;i<=n;i++){
for(int j=;j<;j++){
if((a[i]<a[i-])^j){
f[i][j][]=f[i-][j][]+abs(a[i]-a[i-]);
f[i][j][]=min(f[i-][j][],
min(f[i-][j^][],f[i-][j^][])+m)+abs(a[i]-a[i-]);
}
else{
f[i][j][]=f[i-][j][]+pf(a[i]-a[i-]);
f[i][j][]=min(f[i-][j][],
min(f[i-][j^][],f[i-][j^][])+m)+pf(a[i]-a[i-]);
}
}
}
}
int main(){
n=read();m=read();
for(int i=;i<n;i++) a[i]=read();a[n]=a[];
//情况1、2
memset(f,,sizeof f);memset(f[],0x3f,sizeof f[]);
f[][][]=f[][][]=;;
DP();
Ans=min(min(f[n][][],f[n][][]),min(f[n][][],f[n][][]));
//情况3
memset(f,,sizeof f);memset(f[],0x3f,sizeof f[]);
f[][][]=;
DP();Ans=min(Ans,f[n][][]-m);
//情况3
memset(f,,sizeof f);memset(f[],0x3f,sizeof f[]);
f[][][]=;
DP();Ans=min(Ans,f[n][][]-m); cout<<Ans;
return ;
}