ABC175E
https://gyazo.com/e57957740dbbd37050b698607cd44710
考えたこと
最小費用流かな？
この条件が難しい
高橋君は通ったマス (スタートとゴールも含む) のアイテムを拾うことができます。ただし、マス目の同じ行では3個までしかアイテムを拾うことができません。通ったマスにアイテムがある場合に、そのアイテムを拾わないことはできます。
公式解説
r, c,に「アイテムを拾った数」を加えて三次元でDP
改めて考えたこと
最小費用流で解く場合でも「3個までしか拾えない」をグラフの頂点で表現しようとすると3次元になる そして最小費用流費用として解くよりDPで解く方が計算量が少ない
そして「3個まで」がなければ「経路の最後の頂点だけからスコアが求まる」というタイプ