题目：https://loj.ac/problem/2292
直接 DP 很难做，主要是有那种 “一个区间内部有很多个别的区间” 的情况。
自己想了一番枚举 max-min 的最大限制，然后在该基础上最小化区间个数之类的。还是不会。
看了题解才会。
考虑再设一个 dp 数组来辅助表示那种麻烦的情况。
值可以离散化！又因为代价与值有关，可以考虑把值放进角标里。
令 f[ i ][ j ] 表示把 [ i , j ] 全取完的最小代价，g[ i ][ j ][ l ][ r ] 表示把 [ i , j ] 取得只剩下值在 [ l , r ] 之间的最小代价。
g[ i ][ j ][ l ][ r ] 转移时讨论一下 j 是否留下。若留下，则从 g[ i ][ j-1 ][ l ][ r ] 转移，否则枚举和 j 一起删掉的区间，从 g[ i ][ k-1 ][ l ][ r ] + f[ k ][ j ] 转移。
然后 f[ i ][ j ] 就是各种 g[ i ][ j ][ l ][ r ] 再加上把值在 [ l , r ] 的数一次取完的代价。
这种设状态为 “做到剩下特定元素” 的思想很好。
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int Mx(int a,int b){return a>b?a:b;}
int Mn(int a,int b){return a<b?a:b;}
const int N=,INF=;
int n,m,A,B,a[N],tp[N],f[N][N],g[N][N][N][N];
int Sqr(int x){return x*x;}
void cz(int &u,int v){if(v<u)u=v;}
int main()
{
scanf("%d%d%d",&n,&A,&B);
for(int i=;i<=n;i++)scanf("%d",&a[i]),tp[i]=a[i];
sort(tp+,tp+n+); m=unique(tp+,tp+n+)-tp-;
for(int i=;i<=n;i++)a[i]=lower_bound(tp+,tp+m+,a[i])-tp;
memset(g,0x3f,sizeof g);
for(int i=;i<=n;i++)
{
f[i][i]=A;
for(int l=;l<=m;l++)
for(int r=l;r<=m;r++)
{
if(a[i]>=l&&a[i]<=r)g[i][i][l][r]=;
else g[i][i][l][r]=A;
}
}
for(int d=;d<n;d++)
for(int i=;i+d<=n;i++)
{
int j=i+d; int mx=,mn=INF;
for(int k=i;k<=j;k++)
mx=Mx(mx,a[k]),mn=Mn(mn,a[k]);
f[i][j]=A+B*Sqr(tp[mx]-tp[mn]);
for(int l=;l<=m;l++)
for(int r=l;r<=m;r++)
{
if(a[j]>=l&&a[j]<=r)
cz(g[i][j][l][r],g[i][j-][l][r]);
for(int k=i+;k<=j;k++)
cz(g[i][j][l][r],g[i][k-][l][r]+f[k][j]);
cz(f[i][j],g[i][j][l][r]+A+B*Sqr(tp[r]-tp[l]));
}
}
printf("%d\n",f[][n]);
return ;
}