Educational Codeforces Round 17 D. Maximum path

お題箱より。

Problem - D - Codeforces

問題概要

$3$ 行 $n$ 列のグリッドが与えられ、各マスには整数（非負とは限らない） $a_{ij}$ が書かれている。

左上のマスからスタートし、隣り合うマスを辿って右下のマスまで移動する経路であって、同じマスを複数回通るものがないものを考える。このとき通ったマスに書かれた値の合計を経路のスコアとする。スコアの最大値を求めよ。

制約

$1 \le n \le 10^{5}$
$-10^{9} \le a_{ij} \le 10^{9}$

解法

行数が3本しかないことを利用してDPをします。

もし左に引き返せないルールだったら、単に「 $i-1$ 列目まで見終わって、 $i-1$ 列目から出る時点で $j$ 行目にいる時の、それまでのスコアの最大値」を持ってDPすれば良いです。ただし今回は引き返すことが可能であるため、以下のようにDPの状態を定義します。

$dp\lbrack i \rbrack\lbrack j \rbrack\lbrack k \rbrack =$ グリッドを $i-1$ 列目まで見終わって、スタート地点から伸びてきている経路が $j$ 行目にあって、残りの2行がコの字型に伸びてきている（ $k=1$ ）/いない（ $k=0$ ）ときのスコアの最大値

「コの字型に伸びてきている」とは、例えば以下のような状況を指します。

f:id:betrue12:20200521025053p:plain

アイデアとしては、後で右の方から引き返してきてまた右のほうに戻っていくような経路を、スタート地点からの経路とは別に予め作っておきます。こうすることで、わざわざ戻りに行かなくても引き返す経路を考慮して最適なスコアを求められます。

行が3本しかないので、このようなコの字を想定しても考えられるパターンは少ないです。具体的には、コの字が無くてスタートからの経路が0, 1, 2行目にある3パターンと、スタートからの経路が0行目または2行目にあって残りの2行がコの字になっている2パターンで、合計5パターンです。スタートが0行目にあるので、スタートからの経路が1行目にあって0行目と2行目がコの字になっているパターンは存在しません。

このDPにおける $dp\lbrack i \rbrack\lbrack j \rbrack\lbrack k \rbrack$ からの遷移を考えます。