先頭から考えてもいいんだけど、後ろから考えた。
こうして後ろから $i$ を埋めていく。
都市 $i$ で買ったときの最適な売却額 $S_i$ は、都市 $i$ から直接道がつながる都市 $j_1,j_2,...$ の中で、最も $DP[j]$ が高いもの。(無い場合は0とでもしておく)
よって、ここで買った場合は $S_i-A_i$ 円の利益を手にすることができる。
また、$DP[i]=\max(A_i, S_i)$ として更新しておく。
各都市についてこれを調べ、最も利益の高いものが答え。
買った都市と別の都市で売らないといけないので、$DP[j]$ の情報を取得する→利益を求める→$DP[i]$ を更新する という順番に注意。
少し前に、より操作の種類が増えた類題がAGCで出題されていた。(LINK)
愚直には整数の値をそのまま頂点とした幅優先探索やDijkstraで解けるが、$X,Y$ が大きすぎるのでアウト。
ここで操作の性質に着目すると、「2倍してから+1を2回」するくらいなら「+1してから2倍」した方が絶対によい。
したがって、「一度2倍する操作をしたら、そこからは+1,-1は連続しては使わない」ということがいえる。
これにより、操作を大幅に限定することができる。
しかし、それでも最初に2倍する操作までは何回足したり引いたりすればいいかわからない。
これは、操作を逆から考えることで求めることができる。
こうすると、以下の2種類の操作で、$Y$ を必ず約半分にできる。
そして、$Y$ が十分 $X$ に近づいたら、そのときの $|Y-X|$ が「最初に足したり引いたりすべき回数」となる。
まぁ、「十分近づいたら」といっても厳密にどのタイミングかわかりづらいので、「とりあえず訪れた $Y$ があったら毎回 $|Y-X|$ を計算しといて、その中の最小値が答え」としてよい。 調べるのは $X \le Y$ の間だけでよくて、最大でも $\log_2{10^{18}}=60$ 回程度でたどり着ける。
調べることになる状態数を考える。
$Y$ が奇数の時に2通りに遷移するので、最悪の場合 $2^{60}$ 回程度になる?とか一瞬思ってしまうが、このときに遷移する2つの状態は隣り合っているので、多くがかぶる。
例えば、$Y=63$ とすると、
63 → (31, 32) → (15, 16) → (7, 8) → (3, 4) → (1,2) → 0
というように、2で割った回数が同じ数字は、たかだか2つしかない。よって調べる状態数はせいぜい120通りくらいしかない。