$f[l][r][mi][mx]$表示从l到r发到还没发的部分的最小值为mi最大值为mx时的最小代价。
$f[l][r][0][0]$表示从l到r全部发完的代价。
自己写的无脑dp,枚举中转点k，分成(i,k) (k+1,j)两个区间，分别用mi,mx都在左区间，都在右区间，一个左一个右来转移，这样会发现可以转移过来的都是某个一维或者二维前缀和的形式，于是我开了四个二维数组，暴力维护了6个前缀和更新答案。。。
然后代码就比较鬼畜
//Achen
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<vector>
#include<cstdio>
#include<queue>
#include<cmath>
#include<set>
#include<map>
#define Formylove return 0
#define For(i,a,b) for(int i=(a);i<=(b);i++)
#define Rep(i,a,b) for(int i=(a);i>=(b);i--)
const int N=;
typedef long long LL;
typedef double db;
using namespace std;
int n,sz,w[N],ls[N];
LL a,b,f[N][N][N][N]; template<typename T>void read(T &x) {
char ch=getchar(); x=; T f=;
while(ch!='-'&&(ch<''||ch>'')) ch=getchar();
if(ch=='-') f=-,ch=getchar();
for(;ch>=''&&ch<='';ch=getchar()) x=x*+ch-''; x*=f;
} LL pf(LL x) { return x*x; }
void pre() {
sort(ls+,ls+n+);
sz=unique(ls+,ls+n+)-(ls+);
For(i,,n) w[i]=lower_bound(ls+,ls+sz+,w[i])-ls;
memset(f,/,sizeof(f));
For(i,,n) {
int mi=w[i],mx=w[i];
For(j,i,n) {
mi=min(mi,w[j]);
mx=max(mx,w[j]);
f[i][j][mi][mx]=;
f[i][j][][]=a+b*pf(ls[mx]-ls[mi]);
}
}
} LL p1[N][N],p2[N][N],p3[N][N],p4[N][N],p5,p6;
void clear() {
memset(p1,/,sizeof(p1));
memset(p2,/,sizeof(p2));
memset(p3,/,sizeof(p3));
memset(p4,/,sizeof(p4));
} void get_min(LL &x,LL y) { if(y<x) x=y; } void solve() {
For(len,,n) For(i,,n-len+) {
int j=i+len-;
For(k,i,j-) {
clear();
Rep(mi,sz,) {
p5=p6=1e18;
For(mx,mi,sz) {
p5=min(p5,f[i][k][mi][mx]);
p2[mi][mx]=min(p2[mi][mx],p5);
p6=min(p6,f[k+][j][mi][mx]);
p1[mi][mx]=min(p1[mi+][mx],p6);
p3[mi][mx]=min(p3[mi+][mx],f[k+][j][mi][mx]);
p4[mi][mx]=min(p4[mi+][mx],f[i][k][mi][mx]); get_min(f[i][j][mi][mx],f[i][k][mi][mx]+f[k+][j][][]);
get_min(f[i][j][mi][mx],f[i][k][][]+f[k+][j][mi][mx]); get_min(f[i][j][mi][mx],f[i][k][mi][mx]+p1[mi][mx]);
get_min(f[i][j][mi][mx],p2[mi][mx]+f[k+][j][mi][mx]);
get_min(f[i][j][mi][mx],p5+p3[mi][mx]);
get_min(f[i][j][mi][mx],p4[mi][mx]+p6);
get_min(f[i][j][][],f[i][j][mi][mx]+a+b*pf(ls[mx]-ls[mi]));
}
}
get_min(f[i][j][][],f[i][k][][]+f[k+][j][][]);
}
}
printf("%lld\n",f[][n][][]);
} int main() {
#ifdef ANS
freopen(".in","r",stdin);
freopen(".out","w",stdout);
#endif
read(n);
read(a); read(b);
For(i,,n) read(w[i]),ls[i]=w[i];
pre();
solve();
Formylove;
}
正解的转移非常简单，写出这种转移的人大概和我这种zz之间有着几个世纪的代沟。。。
一开始我的代码wa了才找了个正解来抄，结果还是wa了，最后发现是离散写错了。。。lower_bound里面sz写成了n。。
这里$f[l][r][mi][mx]$应该是从l到r，r一定还没发的最小代价，具体还是看代码吧，感性理解一下
//Achen
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<vector>
#include<cstdio>
#include<queue>
#include<cmath>
#include<set>
#include<map>
#define Formylove return 0
#define For(i,a,b) for(int i=(a);i<=(b);i++)
#define Rep(i,a,b) for(int i=(a);i>=(b);i--)
const int N=;
typedef long long LL;
typedef double db;
using namespace std;
int n,sz,w[N],ls[N];
LL a,b,f[N][N][N][N]; template<typename T>void read(T &x) {
char ch=getchar(); x=; T f=;
while(ch!='-'&&(ch<''||ch>'')) ch=getchar();
if(ch=='-') f=-,ch=getchar();
for(;ch>=''&&ch<='';ch=getchar()) x=x*+ch-''; x*=f;
} LL pf(LL x) { return x*x; }
void pre() {
sort(ls+,ls+n+);
sz=unique(ls+,ls+n+)-(ls+);
For(i,,n) w[i]=lower_bound(ls+,ls+sz+,w[i])-ls;
memset(f,/,sizeof(f));
For(i,,n) {
int mi=w[i],mx=w[i];
For(j,i,n) {
mi=min(mi,w[j]);
mx=max(mx,w[j]);
f[i][j][mi][mx]=;
f[i][j][][]=a+b*pf(ls[mx]-ls[mi]);
}
}
} void get_min(LL &x,LL y) { if(y<x) x=y; } void solve() {
For(len,,n) For(i,,n-len+) {
int j=i+len-;
f[i][j][w[j]][w[j]]=f[i][j-][][];
For(k,i,j-) For(mi,,sz) For(mx,mi,sz)
get_min(f[i][j][min(mi,w[j])][max(mx,w[j])],f[i][k][mi][mx]+(k+<=j-?f[k+][j-][][]:));
For(k,i,j) For(mi,,sz) For(mx,mi,sz)
get_min(f[i][j][][],f[i][k][mi][mx]+a+b*pf(ls[mx]-ls[mi])+(k+<=j?f[k+][j][][]:));
}
printf("%lld\n",f[][n][][]);
} int main() {
#ifdef ANS
freopen(".in","r",stdin);
freopen(".out","w",stdout);
#endif
read(n);
read(a); read(b);
For(i,,n) read(w[i]),ls[i]=w[i];
pre();
//For(i,1,n) printf("%d ",w[i]);
solve();
Formylove;
}
应该算是上一道题的简化版。有了上一次的正解的转移这个就很好写了。思路差不多。$f[l][r][k]$（仅在$a[l]=a[r]$时有意义）表示l和r还没消除，从l到r包括l,r一共有k个和l,r同色的方块还没消除，其他的都消除完了的最大价值。g[l][r]表示l到r全部消除的最大价值。
//Achen
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<vector>
#include<cstdio>
#include<queue>
#include<cmath>
#include<set>
#include<map>
#define Formylove return 0
#define For(i,a,b) for(int i=(a);i<=(b);i++)
#define Rep(i,a,b) for(int i=(a);i>=(b);i--)
const int N=;
typedef long long LL;
typedef double db;
using namespace std;
int T,n,a[N],f[N][N][N],g[N][N]; template<typename T>void read(T &x) {
char ch=getchar(); x=; T f=;
while(ch!='-'&&(ch<''||ch>'')) ch=getchar();
if(ch=='-') f=-,ch=getchar();
for(;ch>=''&&ch<='';ch=getchar()) x=x*+ch-''; x*=f;
} int main() {
#ifdef ANS
freopen(".in","r",stdin);
freopen(".out","w",stdout);
#endif
read(T);
For(cs,,T) {
memset(f,,sizeof(f));
memset(g,,sizeof(g));
read(n);
For(i,,n) read(a[i]);
For(i,,n) g[i][i]=,f[i][i][]=;
For(len,,n) For(i,,n-len+) {
int j=i+len-;
if(a[i]==a[j]) {
For(k,i,j-) if(a[k]==a[j]) {
For(l,,k-i+) if(f[i][k][l]>=) {
f[i][j][l+]=max(f[i][j][l+],f[i][k][l]+(k+<=j-?g[k+][j-]:));
}
}
For(l,,j-i+)
g[i][j]=max(g[i][j],f[i][j][l]+l*l);
}
For(k,i,j-)
g[i][j]=max(g[i][j],g[i][k]+g[k+][j]);
}
printf("Case %d: %d\n",cs,g[][n]);
}
Formylove;
}
之前还以为自己dp学的还可以，现在看来还是太肤浅了