ABC197 E - Traveler (500)
ボールの色毎に位置を持っておく
ボールを回収する際に飛ばす必要は無く、最後に取るボールは左端か右端になる
飛ばした場合、左端か右端を取ってからそのボールを取ることになり無駄
$ dp[i][j] でi番目のボールを取って左端or右端を最後にした場合の最小値とする
考えられる移動は以下の4つ
前回の左端→今回の右端→今回の左端
前回の左端→今回の左端→今回の右端
前回の右端→今回の右端→今回の左端
前回の右端→今回の左端→今回の右端
最終地点が左端・右端共に遷移が2つあるので小さい方の値で更新する
最も色が大きいボールについて上のDPの値とそこからの原点への距離の和の小さい方が答え
色毎の最小値最大値もDPの更新も$ O(N)