集训队作业居然有 *2500 的题。/jy/jy/jy

把贡献拆一下，$f(i,j)$ 中 $i,j$ 的贡献是独立的，很方便我们分别考虑计算。

具体来说贡献有四类：

• 左边比 $i$ 大：$-x_i+b_i$；
• 左边比 $i$ 小：$x_i+c_i$；
• 右边比 $i$ 大：$-x_i+d_i$；
• 右边比 $i$ 小： $x_i+a_i$。

然后按照 JOI 摩天大楼 那个题的套路来做，$dp_{i,j}$ 表示填了前 $i$ 个数，当前有 $j$ 个连续段的最小值。

从小到大加入数字，转移分三类讨论：

• 当前点是 $s$，分成新开一段（右边比他大）和接在一段边上（右边比他小）两种；
• 当前点是 $e$，分成新开一段（左边比他大）和接在一段边上（左边比他小）两种；
• 当前点是普通点，分成新开一段（左右都比他大），合并两段（左右都比他小），接在一段左边（左边比他大，右边比他小），接在一段右边（左边比他小，右边比他大）四种。

这里有一个坑点是有些状态是不合法的，具体来说有下面五种，要特判掉：

• 数组越界了的；
• 合并成 $0$ 段的；
• $s,e$ 都已经填了，当前点不是 $n$ 却已经缩成了一段的；
• 只填了 $s$，只有一段却接在了这段左边的；
• 只填了 $e$，只有一段却接在了这段右边的。

时间复杂度 $O(n^2)$。

#include<iostream>
#include<cstdio>
using namespace std;
#define int long long
int n,s,t,cnt,x[5001],a[5001],b[5001],c[5001],d[5001],dp[5001][5001];
signed 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];
    for(int i=1;i<=n;++i)
        cin>>b[i];
    for(int i=1;i<=n;++i)
        cin>>c[i];
    for(int i=1;i<=n;++i)
        cin>>d[i];
    for(int i=0;i<=n;++i)
        for(int j=0;j<=n;++j)
            dp[i][j]=1e18;
    dp[0][0]=0;
    for(int i=0;i<n;++i)
    {
        for(int j=0;j<=n;++j)
        {
            if(j==1&&cnt==2)
                dp[i][j]=1e18;
            if(dp[i][j]<1e18)
            {
                if(s==i+1)
                {
                    if(j<n)
                        dp[i+1][j+1]=min(dp[i+1][j+1],dp[i][j]-x[i+1]+d[i+1]);
                    if(j)
                        dp[i+1][j]=min(dp[i+1][j],dp[i][j]+x[i+1]+c[i+1]);
                }
                else if(t==i+1)
                {
                    if(j<n)
                        dp[i+1][j+1]=min(dp[i+1][j+1],dp[i][j]-x[i+1]+b[i+1]);
                    if(j)
                        dp[i+1][j]=min(dp[i+1][j],dp[i][j]+x[i+1]+a[i+1]);
                }
                else
                {
                    if(j<n)
                        dp[i+1][j+1]=min(dp[i+1][j+1],dp[i][j]-x[i+1]+b[i+1]-x[i+1]+d[i+1]);
                    if(j>1)
                        dp[i+1][j-1]=min(dp[i+1][j-1],dp[i][j]+x[i+1]+a[i+1]+x[i+1]+c[i+1]);
                    if(j)
                    {
                        if(t>i+1||j>1)
                            dp[i+1][j]=min(dp[i+1][j],dp[i][j]+d[i+1]+a[i+1]);
                        if(s>i+1||j>1)
                            dp[i+1][j]=min(dp[i+1][j],dp[i][j]+c[i+1]+b[i+1]);
                    }
                }
            }
        }
        cnt+=s==i+1||t==i+1;
    }
    cout<<dp[n][1]<<'\n';
    return 0;
}