アルゴリズム忘備録

競技プログラミングとかデータ分析とか

SRM719 Div1 Easy LongMansionDiv1

Webサイトないので貼れない…

 

N行 半無限列のGridが与えられる。各行はコストt[i]が設定されており、行iの任意の列に到着するごとにコストt[i]がかかる(スタート地点もコストがかかる)。最初(sx, sy)にいる人が四方向に1マスずつ移動して(ex, ey)に移動するための最小コストを求めよ。

 

まず分かることは、y方向(左右方向)に移動する行は一つに決まることである。もしそうでなければそれは最小コストではなくなってしまう。なので、その行で総当りする。スタート地点から上下に総当りの行まで移動し、横に移動してまたゴールに上下に移動する、という行動をすることで最小コストがわかる。O(N)。