Codeforces Round #718 Explorer Space - DP

题意

有一个$n \times m$的棋盘。相邻两个各自都有边，每条边都有一个长度。

现在问你，从任意点$(i,j)$出发，走$k$步后回到$(i,j)$所经过的最小长度是多少。过程中可以多次路过$(i,j)$。

题解

首先如果$k$不是偶数，必然无解。

定义$map[i][j][d]$（其中$0 \leq d < 4$）表示$(i,j)$往四个方向的边长。

定义$dp[p][i][j]$表示，从$(i,j)$出发，走$2\cdot p$步回到$(i,j)$的最小开销。

于是有$$dp[p][i][j]=\min\limits_{0 \leq d  < 4} dp[p-1][next_i][next_j]+map[i][j][d]$$其中$next_i$，$next_j$表示从$(i,j)$往$d$方向走一步的坐标。

代码