这是道充分体现了水淹笛卡尔树这个模型的应用的好题。

类似题目：洛谷 P5999，ARC117E

观察这题的权值函数，与排列的相邻元素有关，与元素的大小关系有关。

而笛卡尔树，它的中序遍历记录了位置相关信息，它的拓扑序记录了权值相关信息。

而水淹笛卡尔树，就是一类在笛卡尔树上按层/权值 DP 的思路。

往往我们并不需要显式地说明笛卡尔树的构型，也有些时候，这类题目可以不用笛卡尔树来理解。

既然是按权值 DP ，我们考虑从小到大插入每个数 。

在 之前，已经插入的数会形成若干个连续段，这些数的贡献是已经计算了的，我们只需知道 与两侧数的大小关系，即可计算 的贡献。

在写方程之前，重写一下题目所给的量：。

那么

考察 的转移：

先考虑 的情况：

1. 把已有的两段接起来，在 时转移，显然 两侧的数小于 ，那么 的贡献就是 ，则有转移 。

2. 新开一段，那么它周围的两个数都大于它，在 且 时无法转移：

   。

3. 接在某一段的左边，在 且 时无法转移：

   。

4. 接在某一段的右边，在 且 时无法转移：

   。

在 或 时，新开一段或接在某一段边上即可。

#include <bits/stdc++.h>
using namespace std;
const int N = 5e3 + 5;
typedef long long ll;
template<typename T> inline void ckmin(T &x,const T &y) { if(x > y) x = y;}
ll f[2][N];
int n,s,t;
int X[N],a[N],b[N],c[N],d[N];
int main()
{
	cin >> n >> s >> t;
	for(int i = 1;i <= n;i++) cin >> X[i];
	for(int i = 1;i <= n;i++) cin >> a[i],a[i] += X[i];
	for(int i = 1;i <= n;i++) cin >> b[i],b[i] -= X[i];
	for(int i = 1;i <= n;i++) cin >> c[i],c[i] += X[i];
	for(int i = 1;i <= n;i++) cin >> d[i],d[i] -= X[i];
	memset(f,0x3f,sizeof f);
	f[0][0] = 0;
	for(int i = 1;i <= n;i++)
	{
		memset(f[i&1],0x3f,sizeof f[i&1]);
		if(i != s && i != t)
			for(int j = 0;j < i;j++)
			{
				ll val = f[(i-1)&1][j];
				if((i < max(s,t)) || j > 1) ckmin(f[i&1][j + 1],val + b[i] + d[i]); // 新开一段
				if(j > 1) ckmin(f[i&1][j - 1],val + a[i] + c[i]);
				if(j > 0 && (j > 1 || i < s)) ckmin(f[i&1][j],val + c[i] + b[i]);
				if(j > 0 && (j > 1 || i < t)) ckmin(f[i&1][j],val + a[i] + d[i]);
			}
		if(i == s)
			for(int j = 0;j < i;j++)
			{
				ll val = f[(i-1)&1][j];
				// 新开一段或贴在左边
				ckmin(f[i&1][j+1],val + d[i]);
				if(j > 0) ckmin(f[i&1][j],val + c[i]);
			}
		if(i == t)
			for(int j = 0;j < i;j++)
			{
				ll val = f[(i-1)&1][j];
				ckmin(f[i&1][j+1],val + b[i]);
				if(j > 0) ckmin(f[i&1][j],val + a[i]);
			}
	}
	cout << f[n&1][1] << endl;
	return 0;
}