题目大意
s和e给出
题解
BCDE都是集训队作业真几把吓人
如果没做过类似的题基本不可能做出来
https://www.cnblogs.com/gmh77/p/12208133.html
排列+相邻计算贡献=折线=从下往上dp维护边界
设f[i][j]表示放了前i个有j个边界,显然j<=n所以不用滚动
要注意一下放在某个块的左/右侧的时候要保证这个块存在
code
#include <bits/stdc++.h>
#define fo(a,b,c) for (a=b; a<=c; a++)
#define fd(a,b,c) for (a=b; a>=c; a--)
#define min(a,b) (a<b?a:b)
#define ll long long
//#define file
using namespace std;
ll x[5001],a[5001],b[5001],c[5001],d[5001],f[5001][5001];
int n,i,j,k,l,st,ed;
int main()
{
#ifdef file
freopen("CF704B.in","r",stdin);
#endif
scanf("%d%d%d",&n,&st,&ed);
fo(i,1,n) scanf("%I64d",&x[i]);
fo(i,1,n) scanf("%I64d",&a[i]);
fo(i,1,n) scanf("%I64d",&b[i]);
fo(i,1,n) scanf("%I64d",&c[i]);
fo(i,1,n) scanf("%I64d",&d[i]);
memset(f,127,sizeof(f));f[0][0]=0;
fo(i,1,n)
{
l=i!=1;
fo(j,l,n)
if (f[i-1][j]<8223372036854775807ll)
{
if (i==st)
{
if (j<n) f[i][j+1]=min(f[i][j+1],f[i-1][j]+(-x[i]+d[i]));
if (j>0) f[i][j-1]=min(f[i][j-1],f[i-1][j]+(x[i]+c[i]));
}
else
if (i==ed)
{
if (j<n) f[i][j+1]=min(f[i][j+1],f[i-1][j]+(-x[i]+b[i]));
if (j>0) f[i][j-1]=min(f[i][j-1],f[i-1][j]+(x[i]+a[i]));
}
else
{
if (j+1<n) f[i][j+2]=min(f[i][j+2],f[i-1][j]+(-x[i]+b[i])+(-x[i]+d[i]));
if (j>1 || i>st) f[i][j]=min(f[i][j],f[i-1][j]+(a[i]+d[i]));
if (j>1 || i>ed) f[i][j]=min(f[i][j],f[i-1][j]+(c[i]+b[i]));
if (j-1>0) f[i][j-2]=min(f[i][j-2],f[i-1][j]+(x[i]+a[i])+(x[i]+c[i]));
}
}
}
printf("%I64d
",f[n][0]);
fclose(stdin);
fclose(stdout);
return 0;
}