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