一道非常好的区间 dp。
一开始我理解错了题意，认为只是把原序列分成几个小段，但是发现不是，在发现两边的区间可以合并的时候，我意识到这是一道区间 dp。
1 状态设计
于是我开始考虑状态设计，先按照区间 dp 模板：设 (f_{l,r}) 表示 (l) 到 (r) 这个区间的最优解。然后我们考虑这个区间是否能够包含所有情况，即在这个状态的基础上能否转移。
不难发现仅凭借这个状态是没有办法转移的。我们看看还缺少什么。
其实最特殊的情况实际上是这种情况：区间 ([l,r]) 中有若干段完成的区间，剩下的部分合并起来一起消掉。
由于代价的计算方式，所以实际上我只需要关注剩下部分的最大值和最小值是多少。
于是我们初步设计出来一个状态：(f_{l,r,x,y}) 表示区间 ([l,r])，没选的（就是剩下的部分，我们先不算代价）最小值和最大值分别是 (x,y)。那么考虑这个状态一定会有不合法状态，我们把不合法状态统一设为 (inf)。
2 转移
考虑转移，不难发现，状态 (f_{l,r,x,y}) 包含的所有情况我们可以划分成两个集合，其中一个集合最右边有剩下的部分，那么这个部分的转移我们可以从 (f_{l,r-1,x',y'}) 转移过来，其中 (x=min(x',a_r),y=max(y',a_r))。另一个集合最右边没有剩下的部分，我们考虑枚举 (k)。也就是说，我们枚举所有剩下的部分都来自 ([l,k])。那么右边的代价应该是多少？不难发现，应该是 (minlimits_{x,y}{ f_{k+1,r,x,y}+A+B imes (y-x)^2 })。我们令 (g_{k+1,r}) 等于右式。至于 (g_{l,r}) 的更新，在计算完 (f_{l,r,x,y}) 后更新即可。
最后的答案不难发现是 (g_{1,n})。
3 代码
#include<bits/stdc++.h>
#define dd double
#define ld long double
#define ll long long
#define uint unsigned int
#define ull unsigned long long
#define N 51
#define M number
using namespace std;
const int INF=0x3f3f3f3f;
template<typename T> inline void read(T &x) {
x=0; int f=1;
char c=getchar();
for(;!isdigit(c);c=getchar()) if(c == '-') f=-f;
for(;isdigit(c);c=getchar()) x=x*10+c-'0';
x*=f;
}
template<typename T> inline T Min(T a,T b){return a<b?a:b;}
template<typename T> inline T Max(T a,T b){return a<b?b:a;}
int n,a[N],A,B,b[N],id[N];
int f[N][N][N][N],g[N][N];
int main(){
// freopen("my.in","r",stdin);
// freopen("my.out","w",stdout);
read(n);read(A);read(B);
for(int i=1;i<=n;i++){
read(a[i]);b[i]=a[i];
}
sort(b+1,b+n+1);int w=unique(b+1,b+n+1)-b-1;
for(int i=1;i<=n;i++){
int c=lower_bound(b+1,b+w+1,a[i])-b;
id[c]=a[i];a[i]=c;
}
memset(f,INF,sizeof(f));
memset(g,INF,sizeof(g));
for(int i=1;i<=n;i++){
f[i][i][a[i]][a[i]]=0;
g[i][i]=A;
}
for(int i=2;i<=n;i++){
for(int j=1;j<=n-i+1;j++){
int l=j,r=j+i-1;
for(int mi=1;mi<=w;mi++){
for(int mx=mi;mx<=w;mx++){
f[l][r][Min(mi,a[r])][Max(mx,a[r])]=Min(f[l][r][Min(mi,a[r])][Max(mx,a[r])],f[l][r-1][mi][mx]);
}
}
for(int mi=1;mi<=w;mi++){
for(int mx=mi;mx<=w;mx++){
for(int k=l;k<=r;k++){
f[l][r][mi][mx]=Min(f[l][r][mi][mx],f[l][k][mi][mx]+g[k+1][r]);
}
}
}
for(int mi=1;mi<=w;mi++){
for(int mx=mi;mx<=w;mx++){
g[l][r]=Min(g[l][r],f[l][r][mi][mx]+A+B*(id[mx]-id[mi])*(id[mx]-id[mi]));
}
}
}
}
printf("%d
",g[1][n]);
return 0;
}