Making X

$f(x)$를 $0$에서 시작하여 $x$를 만드는 최소 비용이라고 하자. $X$가 작다면 다음 점화식을 왼쪽부터 계산할 수 있다.

$$f(x)=\min\left(\min_{1\leq i\leq \min(K,x)}(f(x-i)+A_i),\ [x\text{가 짝수}]\,(f(x/2)+B)\right).$$

하지만 $X$가 매우 크므로 필요한 값의 범위를 줄여야 한다.

1. 마지막 두 배 연산 뒤의 덧셈

최적 연산열이 두 배 연산을 한 번 이상 사용한다고 하자. 마지막 두 배 연산 이후에 같은 종류의 연산 $p\mathrel{+}=i$가 두 번 등장할 수 없다.

실제로 마지막 두 배 연산 직전의 값이 $y$이고, 그 뒤에 $+i$가 두 번 등장한다면, 두 번의 $+i$를 지우고 마지막 두 배 연산 직전에 $+i$를 한 번 수행할 수 있다.

$$2(y+i)=2y+2i$$

결과는 같지만 비용은 $2A_i$에서 $A_i$로 감소하므로 기존 연산열은 최적일 수 없다.

따라서 마지막 두 배 연산 이후에 더해지는 값의 합은

$$S=1+2+\cdots+K=\frac{K(K+1)}2$$

이하이다.

2. 덧셈 연산만 사용하는 비용

$C(x)$를 덧셈 연산만 사용하여 $x$를 만드는 최소 비용이라고 하자. 작은 $x$에 대해서는 완전 배낭 점화식으로 계산할 수 있다.

$A_q/q$가 최소가 되는 $q$를 하나 고른다. 나머지를 $q$로 본 그래프를 생각하고, $+i$에

$$qA_i-iA_q$$

의 가중치를 준다. $q$의 선택에 의해 모든 가중치는 음이 아니다. 같은 나머지를 두 번 방문하는 부분은 제거한 뒤 그 양만큼 $+q$로 채울 수 있으므로, 각 나머지에 대한 최적 경로는 $q-1$개 이하의 간선만 사용하도록 고를 수 있다. 이 경로가 더하는 값은 최대 $K(q-1)$이다.

따라서 $0\leq t\leq K(q-1)$에 대한 $C(t)$만 계산하면, 충분히 큰 $x$에 대해 $r=x\bmod q$라 할 때

$$C(x)=\frac{x-r}{q}A_q+ \min_{\substack{0\leq t\leq K(q-1)\\t\bmod q=r}} \left(C(t)-\frac{t-r}{q}A_q\right)$$

로 $C(x)$를 $O(1)$에 구할 수 있다. 계산 중 매우 큰 덧셈 전용 비용은 충분히 큰 값으로 잘라 두어도 된다.

3. 필요한 구간만 재귀적으로 계산하기

구간 $[L,R]$의 모든 $f(x)$가 필요하다고 하자. $x\in[L,R]$의 최적 연산열이 두 배 연산을 사용한다면, 마지막 두 배 연산 직후의 값은 $x-S$ 이상이다. 따라서 마지막 두 배 연산 직전의 값으로 필요한 범위는

$$\left[\left\lceil\frac{\max(0,L-S)}2\right\rceil,\left\lfloor\frac R2\right\rfloor\right]$$

뿐이다.

이 절반 크기의 구간을 재귀적으로 계산한다. 그 뒤 $J=[\max(0,L-S),R]$의 각 위치를 다음 값으로 초기화한다.

• 덧셈만 사용하는 경우의 비용 $C(x)$.
• $x$가 짝수라면, $f(x/2)+B$.

이후 $J$를 왼쪽부터 보면서 모든 $1\leq i\leq K$에 대해 $x$에서 $x+i$로 비용 $A_i$의 전이를 한다. 모든 전이는 값이 증가하는 방향이므로 한 번의 순회로 최단 거리를 계산할 수 있다. 마지막에 $[L,R]$에 해당하는 부분만 반환한다.

처음에는 구간 $[X,X]$만 요청한다. 재귀 단계에서 구간의 길이를 $W$라 하면 다음 단계의 길이는 대략 $(W+S)/2$이므로 항상 $O(S)$이고, 재귀 깊이는 $O(\log X)$이다. 각 단계에서 길이 $O(S)$인 구간에 대해 $K$개의 덧셈 전이를 확인하므로 전체 시간 복잡도는

$$O(KS\log X)=O(K^3\log X)$$

이고, 메모리 복잡도는 $O(S+K^2)$이다.

Solution written by GPT5.6