BOJ 27480 Even Harder

DP를 다음과 같이 정의합니다.

• $f(i, j)$: $i$번째에서 시작하여 $n$번째에 도달하는 유일한 경로에서 $i$ 다음에 $j$를 밟아야 할 때 $a_{i+1}, \cdots, a_n$ 중에서 0으로 바꾼 수의 최소 개수; 그러한 방법이 존재하지 않으면 $\infty$

그러면 다음과 같은 식을 만들 수 있습니다. 편의상 $i$에서 도달 가능한 최대 지점 $i + a_i$를 $b_i$라고 합시다. $[x]$는 Iverson bracket으로, 조건 $x$가 참이면 1, 아니면 0입니다.

• $b_i \ge i+1$이라면, $f(i, i+1) = \min_{b_i + 1 \le j \le b_{i+1}} f(i+1, j)$. $j$에서 다음으로 밟는 위치가 $b_i$ 이하이면 $i$에서 바로 그 지점을 밟는 경로가 생기므로, 그 위치는 $b_i$보다는 커야 합니다.
• $b_i \ge i+2$이라면, $f(i, i+2) = \min_{b_i + 1 \le j \le b_{i+2}} f(i+2, j) + [b_{i+1} \ge i+2]$. $i$에서 $i+2$로 갈 수 있다는 것은 $i+1$로도 갈 수 있다는 것으로, $i+1$에서 $i+2$로 갈 수 있으면 추가 경로가 생기므로 $a_{i+1}$을 0으로 만들어서 끊어줘야 합니다.
• $b_i \ge i+3$이라면, $f(i, i+3) = \min_{b_i + 1 \le j \le b_{i+3}} f(i+3, j) + [b_{i+1} \ge i+3] + [b_{i+2} \ge i+3]$. 먼저 $i+2$에서 $i+3$으로 가는 경로는 반드시 끊어야 하고, 이제 $i+1$에서 $i+2$를 거쳐 $i+3$으로 갈 수는 없으므로 $i+1$에서 바로 $i+3$으로 갈 수 있는지만 체크해서 끊어주면 됩니다.
• 이를 일반화하면 다음의 식을 얻습니다. $b_i \ge i+k \Rightarrow f(i, i+k) = \min_{b_i + 1 \le j \le b_{i+k}} f(i+k, j) + \sum_{1 \le j < k} [b_{i+j} \ge i+k]$
• 이는 $f(i, j)$의 누적 min과 $[b_i \ge j]$의 누적합을 이용하여 구할 수 있습니다.
• 예외적으로 다음 목적지가 $n$인 경우는 더 이상 갈 곳이 없으므로 $f(i, n) = \sum_{i+1 \le j < n} [b_{j} \ge n]$으로 구할 수 있습니다.