【Codeforces 704B】Ant Man
mrsrz
1月 14, 2020
DP。
题目大意：
给定数轴上的 $n$ 个点的坐标 $x_1,x_2,\ldots,x_n$，保证对于 $i\lt j$ 有 $x_i\lt x_j$。
对每个点有四个参数 $a_i,b_i,c_i,d_i$。
给出 $s,e$，要求找到 $s$ 到 $e$ 且经过每个点恰好一次的路径，使得路径长度最小。
两个点之间的路径 $\mathrm{dist}(i,j)$ 定义如下：
题解：
首先将 $a,b,c,d$ 处理过后就不需要考虑 $x$ 的影响了，可以得到新的距离计算方式：
发现对于一个点，它的贡献只和它的入边以及出边的方向有关。所以可以不需要管点的连接顺序，只需要考虑一个点的入边和出边的方向，并保证最后能够匹配就可以了。
最终的情况一定是从 $s$ 到 $e$ 的一条链的形式，而中间可以有多条链。我们记录当前的链的条数即可。
令 $f_{i,j}$ 表示当前考虑点 $i$，之前已经存在 $j$ 条链的最小贡献。
考虑一个点的四种情况：
- 入边从左边过来，出边向左边出去。这种情况会将两条链合并，当 $j\gt 1$ 时，$f_{i,j-1}\leftarrow f_{i-1,j}+a_i+c_i$。
- 入边从右边过来，出边向右边出去。这种情况会新产生一条链并作为它的开端。$f_{i,j+1}=f_{i-1,j}+b_i+d_i$。
- 入边从左边过来，出边向右边出去。这种情况不会使链的条数发生改变。$f_{i,j}=f_{i-1,j}+a_i+d_i$，并且要保证至少存在一条不是以 $e$ 结尾的链。
- 入边从右边过来，出边向左边出去。这种情况不会使链的条数发生改变。$f_{i,j}=f_{i-1,j}+b_i+c_i$，并且要保证至少存在一条不是以 $s$ 开头的链。
如果 $i=s$ 或 $i=e$ 则需要特殊判断只有出边/入边的情况。
又因为当 $s$ 或 $e$ 出现时至少存在两条链并且到最后才合并，因此 $j$ 要从 $[i>s]+[i>e]$ 开始枚举。
最后答案为 $f_{n,1}$。
时间复杂度 $O(n^2)$。
Code：
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long LL;
const int N=5005;
LL F[2][N];
int n,X[N],A[N],B[N],C[N],D[N],s,e;
inline void chkmin(LL&a,const LL&b){a=min(a,b);}
int main(){
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);
for(int i=1;i<=n;++i)
C[i]+=X[i],B[i]-=X[i],D[i]-=X[i],A[i]+=X[i];
memset(F,0x3f,sizeof F);
F[0][0]=0;
for(int i=1;i<=n;++i){
LL*f=F[i&1],*g=F[i&1^1];
memset(f,0x3f,sizeof*F);
for(int p=0;p<=i;++p){
if(i==s){
if(p<(i>e))continue;
if(p)chkmin(f[p],g[p]+C[i]);
chkmin(f[p+1],g[p]+D[i]);
}else if(i==e){
if(p<(i>s))continue;
if(p)chkmin(f[p],g[p]+A[i]);
chkmin(f[p+1],g[p]+B[i]);
}else{
if(p<(i>s)+(i>e))continue;
chkmin(f[p+1],g[p]+B[i]+D[i]);
if(p>1)chkmin(f[p-1],g[p]+A[i]+C[i]);
if(p>(i>e))chkmin(f[p],g[p]+A[i]+D[i]);
if(p>(i>s))chkmin(f[p],g[p]+B[i]+C[i]);
}
}
}
printf("%lld\n",F[n&1][1]);
return 0;
}