区间dp（刷表法转移）：P5336

本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/135028996

https://www.luogu.com.cn/problem/P5336

离散化后枚举 g(l,r,mn,mx)g(l,r,mn,mx) ，和 f(l,r)f(l,r) （全删情况），然后考虑使用刷表法来转移。

  1. ar+1a_{r+1} 加进来，更新 mn,mxmn,mx 即可

  2. 不加进来，停表，干脆枚举分界点来转移（因为要从小加到大）。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#include<bits/stdc++.h>
using namespace std;
#ifdef LOCAL
 #define debug(...) fprintf(stdout, ##__VA_ARGS__)
#else
 #define debug(...) void(0)
#endif
//#define int long long
inline int read(){int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;
ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+
(x<<3)+(ch^48);ch=getchar();}return x*f;}
#define Z(x) (x)*(x)
#define pb push_back
#define fi first
#define se second
//#define M
//#define mo
#define N 55
void Mn(int &a, int b) { a=min(a, b); }
int n, m, i, j, k, T;
int f[N][N], g[N][N][N][N], l, r, len, A, B;
int a[N], b[N]; 

signed main()
{
	#ifdef LOCAL
	  freopen("in.txt", "r", stdin);
	  freopen("out.txt", "w", stdout);
	#endif
//	srand(time(NULL));
//	T=read();
//	while(T--) {
//
//	}
	n=read(); A=read(); B=read();  
	for(i=1; i<=n; ++i) a[i]=b[i]=read(); 
	sort(b+1, b+n+1); 
	for(i=1; i<=n; ++i) a[i]=lower_bound(b+1, b+n+1, a[i])-b; 
	memset(g, 0x3f, sizeof(g)); 
	memset(f, 0x3f, sizeof(f)); 
	for(i=1; i<=n; ++i) g[i][i][a[i]][a[i]]=0; 
	for(len=1; len<=n; ++len)
		for(l=1, r=len; r<=n; ++l, ++r) 
			for(i=1; i<=n; ++i) for(j=i; j<=n; ++j) {
				for(k=l; k<r; ++k) Mn(g[l][r][i][j], g[l][k][i][j]+f[k+1][r]); 
				Mn(f[l][r], g[l][r][i][j]+A+B*Z(b[j]-b[i])); 
				if(r<n) Mn(g[l][r+1][min(i, a[r+1])][max(j, a[r+1])], g[l][r][i][j]); 
			}
	printf("%lld\n", f[1][n]); 
	return 0;
}