# Description

Luogu 传送门

# Solution

区间 dp

根据套路，我们定义 $dp[i][j]$ 表示取走区间 $[i, j]$ 的最小花费。

但是只有区间范围似乎并不好转移，因为我们也不知道区间最大值以及最小值是多少。

所以我们再定义一个 $f[i][j][x][y]$ 数组，表示区间 $[i, j]$ 中所有数在区间 $[x, y]$ 时，需要的最小花费。

注意：这里 $f[i][j][x][y]$ 中不一定 $[i, j]$ 中的最小值和最大值就是 $x$ 和 $y$ 。

这里还要进行分类讨论：

	f[i][j][min(x, a[j])][max(y, a[j])] = min(f[i][j][min(x, a[j])][max(y, a[j])], f[i][j - 1][x][y]);
	f[i][j][min(x, a[i])][max(y, a[i])] = min(f[i][j][min(x, a[i])][max(y, a[i])], f[i + 1][j][x][y]);

枚举断点 $k$ ，先把 $[i, k]$ 合并好之后再和 $[k + 1, j]$ 合并（此时 $[k + 1, j]$ 还没有合并），或先把 $[k + 1, j]$ 合并好之后再和 $[i, k]$ 合并（同理）。

	for(ll k = i; k < j; k++)
	f[i][j][x][y] = min(f[i][j][x][y], min(f[i][k][x][y] + dp[k + 1][j], f[k + 1][j][x][y] + dp[i][k]));

不过好像只转移同一个方向的就够了，不知道为什么 $QwQ$ 。

注意开 $long \ long$ ，以及要先进行离散化。

	#include <iostream>
	#include <cstdio>
	#include <algorithm>
	#include <cstring>
	#define ll long long

	using namespace std;

	const ll N = 55;
	ll n, A, B;
	ll a[N], b[N];
	ll f[N][N][N][N], dp[N][N];

	signed main(){
	scanf("%lld%lld%lld", &n, &A, &B);
	for(ll i = 1; i <= n; i++)
	scanf("%lld", &a[i]), b[i] = a[i];
	sort(b + 1, b + 1 + n);
	ll tot = unique(b + 1, b + 1 + n) - b - 1;
	memset(f, 0x3f, sizeof(f));
	memset(dp, 0x3f, sizeof(dp));
	for(ll i = 1; i <= n; i++){
	a[i] = lower_bound(b + 1, b + 1 + tot, a[i]) - b;
	f[i][i][a[i]][a[i]] = 0;
	dp[i][i] = A;
	}
	for(ll len = 2; len <= n; len++)
	for(ll i = 1; i + len - 1 <= n; i++){
	ll j = i + len - 1;
	for(ll x = 1; x <= tot; x++)
	for(ll y = 1; y <= tot; y++){
	f[i][j][min(x, a[j])][max(y, a[j])] = min(f[i][j][min(x, a[j])][max(y, a[j])], f[i][j - 1][x][y]);
	f[i][j][min(x, a[i])][max(y, a[i])] = min(f[i][j][min(x, a[i])][max(y, a[i])], f[i + 1][j][x][y]);
	for(ll k = i; k < j; k++)
	f[i][j][x][y] = min(f[i][j][x][y], min(f[i][k][x][y] + dp[k + 1][j], f[k + 1][j][x][y] + dp[i][k]));
	}
	for(ll x = 1; x <= tot; x++)
	for(ll y = 1; y <= tot; y++)
	dp[i][j] = min(dp[i][j], f[i][j][x][y] + A + B * (b[y] - b[x]) * (b[y] - b[x]));
	}
	printf("%lld\n", dp[1][n]);
	return 0;
	}