점프

summary: 0에서 시작해서 $1,2,4,8,\dots$ 처럼 이전에 뛰었던 수의 2배로 뛰던지, 다시 1로 뛰던지 두 가지 operation중에 하나를 사용해서 가장 적은 횟수로 $n$까지 도달하는 최소 이동 횟수를 $J(n)$이라고 한다.

쿼리 $(l,r)$이 N개 주어지는데 $l\leq x \leq r$의 범위에서 $J(x)$의 최댓값을 찾는 문제이다.

solution:

$1 \leq l,r \leq 10^9$ 이므로 map을 사용해서 dp를 구현한다.

먼저 이전 2배로 뛰는 행위를 $x$번 하면 $2^x-1$만큼 이동할수 있고, $2^{30}-1>10^9$이므로 30번만 뛰어도 범위를 벗어난다.

d(l,r): (l,r)범위에서 J의 최댓값 으로 정의하면 점화식은 다음과 같다.

$d(l,r)= max_{1\leq k \leq 30}(d(l-2^k,r-2^k)+k)$ ($l \neq 0$, $r \neq 0$)

$d(l,r)=0 (l=0,r=0) $