D

给定一个序列,给定起点和终点
现在要从起点开始,每次可以跳到任意点
每个点都经过且只能经过一次,最后跳到终点

每次跳跃的代价为
$|x_i - x_j| + c_i + b_j \;\; if \; j < i$
$|x_i - x_j| + d_i + a_j \;\; if \; j > i$

DP

$d(i,j,0..3)$ 表示前i个点中,有多少对未匹配的链(I/O 算一对)
由于有起点和终点的情况,所以最后一维表示是否有未配对的链

0 表示没有
1 表示有一条出链
2 表示有一条入链

注意只有一条链时的转移…