传送门
solution
容易想到是区间DP，于是考虑\(f_{l,r}\)表示区间\([l,r]\)中的成绩单全部被发放需要的最小代价
但是这道题目的发放成绩单方式比较奇妙，发放一段区间可能可以先在区间中随意选择一些部分来发放，再将剩下的部分发放。
注意到分发代价只与一段区间中分数的\(max\)与\(min\)有关，于是我们令\(g_{l,r,mn,mx}\)为区间\([l,r]\)中的所有成绩单发放一部分后剩下的成绩单的分数最大值为\(mx\)，最小值为\(mn\)时的最小代价
于是有
\[f_{l,r}=min(g_{l,r,mn,mx}+a+b*(mx-mn)^2)
\]
考虑\(g_{l,r,mn,mx}\)加入新成绩单\(r+1\)时的转移
1.保留\(r+1\)的成绩单不取走，未来与\([l,r]\)的部分共同取走
\[g_{l,r+1,min(mn,w[r+1]),max(mx.w[r+1])}=min(g_{l,r,mn,mx})
\]
2.将\([r+1,k]\)这段区间的成绩单共同取走
\[g_{l,k,mn,mx}=min(g_{l,r,mn,mx}+f_{r+1,k})
\]
注意到第一个转移是填表，第二个转移是刷表
于是将第二个转移稍微变化一下变化成
\[g_{l,r,mn,mx}=min(g_{l,k,mn,mx}+f_{k+1,r})
\]
再在区间DP枚举\(len\)时从1开始枚举即可
code
#include<bits/stdc++.h>
using namespace std;
const int N=55;
int n,a,b,w[N],f[N][N],g[N][N][N][N],d[N];
int tot;
int main(){
scanf("%d%d%d",&n,&a,&b);
for(int i=1;i<=n;++i) scanf("%d",&w[i]),d[i]=w[i];
sort(d+1,d+n+1);tot=unique(d+1,d+n+1)-d-1;
for(int i=1;i<=n;++i) w[i]=lower_bound(d+1,d+tot+1,w[i])-d,f[i][i]=a;
memset(g,0x3f,sizeof(g));memset(f,0x3f,sizeof(f));
for(int i=1;i<=n;++i)g[i][i][w[i]][w[i]]=0;
for(int len=1;len<=n;++len)
for(int l=1,r=len;r<=n;++l,++r)
for(int mn=1;mn<=tot;++mn)
for(int mx=mn;mx<=tot;++mx){
int &G=g[l][r][mn][mx];
for(int k=l;k<r;++k) G=min(g[l][k][mn][mx]+f[k+1][r],G);
int &gg=g[l][r+1][min(mn,w[r+1])][max(mx,w[r+1])];
gg=min(gg,G);f[l][r]=min(f[l][r],G+a+b*(d[mx]-d[mn])*(d[mx]-d[mn]));
}
printf("%d\n",f[1][n]);
}