满分做法：
这个状态是我见到过最奇怪的,\(f[i][j][l][r]\)表示在区间\([i,j]\)中取出一些数后,剩下的数值在\([l,r]\)范围内的最小代价。因为\(w[i]<=1000\),这个显然不能存在作为数组下标，所以离散化就好了。
由这个状态可知\(f[i][j][0][0]\)就是将这一段全部取完的最小代价。
考虑转移：
令\(l,r\)离散前的数为\(x,y\)。对于\(f[i][j][0][0]\)的转移有两种情况:
1.一次全部取完：\(f[i][j][0][0]\)=\(a\)+\(b\)*(\(wi\)到\(wj\)的最大值-\(wi\)到\(wj\)的最小值)²。
2.先取完不在\([l,r]\)内的数，剩下的一次取完:\(f[i][j][0][0]=f[i][j][l][r]+a+b*(y-x)²\)，两者取最小值即可。
对于\(f[i][j][l][r]\)的转移，考虑枚举断点\(k\)，则转移有三种情况:
1.左边取完，右边没取完：\(f[i][j][l][r]=f[i][k][0][0]+f[k+1][j][l][r]\)。
2.左边没取完，右边取完：\(f[i][j][l][r]=f[i][k][l][r]+f[k+1][j][0][0]\)。
3.左边没取完，右边没取完：\(f[i][j][l][r]=f[i][k][l][r]+f[k+1][j][l][r]\)。
对于其他情况：当\(i==j\)且\(l<=w[i]<=r\)时,\(f[i][j][l][r]=0\),其他全赋成无穷大。
因为转移的情况会有重复，所以记忆化搜索是一个不错的选择；此外因为搜索时都是区间区间的搜，保证取数是连续的。
#include<cstring>
#include<queue>
#include<cstdio>
#include<iostream>
#include<cmath>
#include<algorithm>
#include<vector>
using namespace std;
typedef long long ll;
const int maxm=57;
const int inf=1e9+7;
int n,a,b,tot;
int w[maxm];
int f[maxm][maxm][maxm][maxm];//f[i][j][l][r]表示在区间[i,j]中取出一些数后,剩下的数值在[l,r]范围内的最小代价
int book[maxm],c[maxm];
bool vis[maxm][maxm][maxm][maxm];
int dfs(int i,int j,int l,int r)//记忆化搜索
{
if(vis[i][j][l][r]) return f[i][j][l][r];
vis[i][j][l][r]=1;
f[i][j][l][r]=inf;
if(l==0&&r==0)
{
int x=inf,y=-inf;
for(int k=i;k<=j;k++)
{
x=min(x,c[k]);
y=max(y,c[k]);
}
f[i][j][0][0]=min(f[i][j][0][0],a+b*(y-x)*(y-x));//一次取空
for(int k=1;k<=tot;k++)
{
for(int p=k;p<=tot;p++)
{
f[i][j][0][0]=min(f[i][j][0][0],dfs(i,j,k,p)+a+b*(book[p]-book[k])*(book[p]-book[k]));//先取完不在l-r的数，在一次取完
}
}
return f[i][j][0][0];
}
else
{
if(i==j)
{
if(w[i]>=l&&w[i]<=r)
f[i][j][l][r]=0;
return f[i][j][l][r];//如果不是0，就是inf
}
for(int k=i;k<=j-1;k++)
{
f[i][j][l][r]=min(f[i][j][l][r],dfs(i,k,0,0)+dfs(k+1,j,l,r));//左边取空
f[i][j][l][r]=min(f[i][j][l][r],dfs(i,k,l,r)+dfs(k+1,j,0,0));//右边取空
f[i][j][l][r]=min(f[i][j][l][r],dfs(i,k,l,r)+dfs(k+1,j,l,r));//左右均取不完
}
return f[i][j][l][r];
}
}
int main()
{
scanf("%d%d%d",&n,&a,&b);
for(int i=1;i<=n;i++)
{
scanf("%d",c+i);
book[i]=c[i];
}
sort(book+1,book+n+1);
tot=unique(book+1,book+n+1)-book-1;
for(int i=1;i<=n;i++)
{
w[i]=lower_bound(book+1,book+tot+1,c[i])-book;
}
printf("%d\n",dfs(1,n,0,0));
return 0;
}