> For the complete documentation index, see [llms.txt](https://solutions.icpc.uclaacm.com/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://solutions.icpc.uclaacm.com/2021-tryout-solutions/tryout-1/i-city-destruction.md).

# 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.​

{% hint style="info" %}
For convenience, set $$e\_0=0$$.
{% endhint %}

* 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&#x20;
  * $$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]$$.

{% hint style="warning" %}
Remember to use long integers to avoid overflow!
{% endhint %}