この問題は区間 DP で解くことができます。

点 \(0\) を \((0,0)\) とします。 また、 \(0 \le l \le r \le N\) に対して、 \(P_{l, r} = (X(l, r), Y(l, r)) = (\min_{l\le i\le r}X_i, \min_{l\le i\le r}Y_i)\) とします。

\(dp[l][r]=\) \(S\) が空文字列で \(P_{l, r}\) にいるときに、点 \(l\) から \(r\) までをこの順にすべて訪れるときの最小コストとします。求める答えは \(dp[0][n]\) です。

\(S\) が空文字で \((x, y)\) から始めて点 \(l, \dots, r\) を訪れる最小コストは

• \(x \le X(l, r)\) かつ \(y \le Y(l, r)\) のとき、 \(X(l, r)-x+Y(l, r)-y + dp[l][r]\)
• そうでないときは不可能

\(P_{l,r}\) から始めて点 \(l\) から \(r\) までを通る移動で、 \(P_{l,r}\) を通るタイミングを全部試せばよいです。具体的には、 \(l\le i \lt r\) に対して、 \(P_{l, i}\) を通り点 \(l\) から \(i\) までをすべて訪れて \(P_{l,r}\) に戻り、その後、 \(P_{i+1,r}\) を通り点 \(i+1\) から \(r\) までをすべて訪れて \(P_{l,r}\) に戻ってくる最小コストを求めればいいです。

よって、 DP の更新式は以下のようになります。

• \(l = r\) のとき、 \(dp[l][r] = 0\)
• \(l < r\) のとき、 \(dp[l][r] = \min_{l \le i \lt r} dp[l][i] + dp[i+1][r] + X(l, i) + X(i+1, r) - 2X(l, r) + Y(l, i) + Y(i+1, r) - 2Y(l, r)\)

以上から、 \(O(N^3)\) 時間でこの問題を解くことができます。