【题解】CF704B Ant Man
（题目传送门）
一道很好的排列 \(\rm dp\)（连续段 \(\rm dp\)）的题目。
我们考虑从小到大插入这 \(n\) 个数，设 \(f[i][j]\) 表示现在考虑到第 \(i\) 个数，有 \(j\) 个连续段的最小权值，初始化为正无穷。
那么我们在插入一个数 \(i\) 时，要将 \(i\) 可能会产生的贡献提前计算。注意到如果 \(i=s\) 或 \(i=e\) 时贡献会有所不同，所以我们要分情况讨论：
-
\(i=s\)：
-
将 \(i\) 插入到第一个连续段的最前面：
\(f[i-1][j]+x_i+c_i\rightarrow f[i][j]\)
-
将 \(i\) 放在最前面自成一段，注意此时若 \(e\) 已经插入，则要求 \(j\geq 1\)：
\(f[i-1][j]-x_i+d_i\rightarrow f[i][j+1]\)
-
-
\(i=e\)：
-
将 \(i\) 插入到最后一个连续段的最后面：
\(f[i-1][j]+x_i+a_i\rightarrow f[i][j]\)
-
将 \(i\) 放到最后面自成一段，注意此时若 \(s\) 已经插入，则要求 \(j\geq 1\)：
\(f[i-1][j]-x_i+b_i\rightarrow f[i][j+1]\)
-
-
\(i\ne s\) 且 \(i\ne e\)
-
将 \(i\) 插入到左边，注意若 \(s\) 已经插入，则要求 \(j>1\)：
\(f[i-1][j]+b_i+c_i\rightarrow f[i][j]\)
-
将 \(i\) 插入到右边，注意若 \(e\) 已经插入，则要求 \(j>1\)：
\(f[i-1][j]+a_i+d_i\rightarrow f[i][j]\)
-
用 \(i\) 合并两个连续段，此时要求 \(j\geq 2\)：
\(f[i-1][j]+x_i+x_i+a_i+c_i\rightarrow f[i][j-1]\)
-
\(i\) 自成一段，注意若 \(s\) 或 \(e\) 若已经插入则对 \(j\) 有要求：
\(f[i-1][j]-x_i-x_i+b_i+d_i\rightarrow f[i][j+1]\)
-
最后输出 \(f[n][1]\)，那这道题就愉快地结束了！
#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int N=5010;
int n,s,e;
LL f[N][N];
int x[N],a[N],b[N],c[N],d[N];
int main()
{
memset(f,0x3f,sizeof(f));
scanf("%d%d%d",&n,&s,&e);
for(int i=1; i<=n; i++)
scanf("%d",&x[i]);
for(int i=1; i<=n; i++)
scanf("%d",&a[i]);
for(int i=1; i<=n; i++)
scanf("%d",&b[i]);
for(int i=1; i<=n; i++)
scanf("%d",&c[i]);
for(int i=1; i<=n; i++)
scanf("%d",&d[i]);
f[0][0]=0;
for(int i=1; i<=n; i++)
{
for(int j=0; j<i; j++)
{
if(i==s)
{
f[i][j]=min(f[i][j],f[i-1][j]+x[i]+c[i]);
if(j>=(i>e))
f[i][j+1]=min(f[i][j+1],f[i-1][j]-x[i]+d[i]);
}
else if(i==e)
{
f[i][j]=min(f[i][j],f[i-1][j]+x[i]+a[i]);
if(j>=(i>s))
f[i][j+1]=min(f[i][j+1],f[i-1][j]-x[i]+b[i]);
}
else
{
if(j>1 || (i<s && j>0))
f[i][j]=min(f[i][j],f[i-1][j]+b[i]+c[i]);
if(j>1 || (i<e && j>0))
f[i][j]=min(f[i][j],f[i-1][j]+a[i]+d[i]);
if(j>=2)
f[i][j-1]=min(f[i][j-1],f[i-1][j]+x[i]+x[i]+a[i]+c[i]);
if(j>=((i>s)+(i>e)))
f[i][j+1]=min(f[i][j+1],f[i-1][j]-x[i]-x[i]+b[i]+d[i]);
}
}
}
printf("%lld",f[n][1]);
return 0;
}