I: City Destruction

https://open.kattis.com/problems/city

• Let $dp[i][0]$ denote the (minimum) number of moves required to destroy all the cities from $i$ through $N$, assuming that the $(i-1)^{th}$​city (if exists) was not destroyed before the $i^{th}$ city.​

• Let $dp[i][1]$ denote the (minimum) number of moves required to destroy all the cities from $i$ through $N$, assuming that the $(i-1)^{th}$​city (if exists) was destroyed before the $i^{th}$ city.​

For convenience, set $e_0=0$.

• Initial condition:

  • $dp[n][0]=\lceil \frac{h_n}{d} \rceil$, $dp[n][1]=\lceil \frac{max(h_n-e_{n-1},0)}{d} \rceil$

• For $i<n$, it is easy to see that the transitions are

  • $dp[i][0]=min(dp[i+1][0]+\lceil \frac{(max(h_i-e_{i+1},0)}{d} \rceil, dp[i+1][1]+\lceil \frac{h_i}{d} \rceil))$

    • If we assume city $i+1$was destroyed earlier, then our health reduces by $e_{i+1}$and the number of extra moves required is $\lceil \frac{(max(h_i-e_{i+1},0)}{d} \rceil$.

    • Otherwise, the number of extra moves required is $\lceil \frac{h_i}{d} \rceil$.

  • $dp[i][1]=min(dp[i+1][0]+\lceil \frac{(max(h_i-e_{i+1}-e_{i-1},0)}{d} \rceil, dp[i+1][1]+\lceil \frac{max(h_i-e_{i-1},0)}{d} \rceil))$

    • In this case, since city $i-1$ has exploded already, our health has already reduced to $max(h_i-e_{i-1},0)$.

    • If we assume city $i+1$was destroyed earlier, then our health reduces by $e_{i+1}$and the number of extra moves required is $\lceil \frac{(max(h_i-e_{i+1}-e_{i-1},0)}{d} \rceil$.

    • Otherwise, the number of extra moves required is $\lceil \frac{max(h_i-e_{i-1},0)}{d} \rceil$.

• The final answer is $dp[1][0]$.

Remember to use long integers to avoid overflow!