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$方向走一步的坐标。

代码

Submission #114076615 - Codeforces
Codeforces. Programming competitions and contests, programming community
展示评论