Chicken Jockey

The problem looks like a chaotic pile of mobs, but the key is that stacks split, and after splitting, they never merge again. So we should stop trying to simulate Minecraft physics like a sleep-deprived YouTuber and instead ask: what local benefit can one death give to the mob above it?

What fall damage can actually do

Suppose Steve directly kills some mob at position $k$ in its current stack, counting from the bottom of that stack.

Then the mob immediately above it takes $k$ fall damage. If that mob dies too, the next mob above takes only $1$ fall damage, because now it was only above one mob in the newly formed falling stack.

So there are two kinds of useful free damage:

• a big hit of size $k$ to the mob directly above Steve's chosen victim;
• then possibly a chain of $1$ damage hits upward.

That sounds more complicated than it is. The huge observation is that the big hit can only help one adjacent pair: kill lower mob, damage the one right above it. Everything else in the cascade gets at most $1$ damage, which can be handled locally.

DP definition

Let $dp[i]$ be the minimum number of attacks needed to kill the first $i$ mobs, i.e. mobs $1,2,\dots,i$.

We process from bottom to top.

Base cases:

$$dp[0]=0$$

For one mob, Steve just kills it:

$$dp[1]=h_1$$

Now consider how mob $i$ dies.

Option 1: kill mob $i$ normally

Maybe nothing fancy happens with mob $i$. We first kill mobs $1..i-1$ optimally, then spend $h_i$ attacks on mob $i$.

That gives:

$$dp[i] \le dp[i-1]+h_i$$

This transition is boring, but boring is often AC. Sadly, not always.

Option 2: use mob $i-1$ to drop mob $i$

The useful trick is to directly kill mob $i-1$ while mob $i$ is still above it. Then mob $i$ takes fall damage equal to the number of mobs below it in that current stack.

When we are considering the prefix $1..i$, that fall damage can be treated as $i-1$. So after mob $i-1$ dies, mob $i$ still needs:

$$\max(0, h_i-(i-1))$$

attacks.

What about mob $i-1$ itself? It may receive $1$ fall damage when mob $i-2$ dies. That means killing mob $i-1$ costs not $h_{i-1}$, but effectively:

$$\max(1, h_{i-1}-1)$$

Why the $\max(1,\cdot)$? Because Steve still needs some attack to make mob $i-1$ be the directly killed mob that causes mob $i$ to fall. If it already had health $1$ after fall damage, one attack kills it. If the $1$ fall damage would have killed it automatically, then it would not be Steve's chosen cut anymore, so this transition must still pay one attack for that role. Tiny detail, massive wrong-answer trap. Classic Codeforces nonsense.

The mobs below $i-1$ are handled optimally as $dp[i-2]$.

So the pair transition is:

$$dp[i] \le dp[i-2] + \max(1,h_{i-1}-1)+\max(0,h_i-(i-1))$$

Full recurrence

For every $i \ge 2$:

$$dp[i]=\min\left( dp[i-1]+h_i, dp[i-2]+\max(1,h_{i-1}-1)+\max(0,h_i-(i-1)) \right)$$

The answer is $dp[n]$.

Why this is enough

Any useful large fall damage is caused by killing the mob directly below the damaged mob. That means the only special interaction involving mob $i$ is with mob $i-1$.

If mob $i$ does not use that interaction, it is just paid for normally after the prefix below is gone.

If it does use that interaction, then mob $i-1$ must be the cut mob, and everything below $i-1$ is independent, already represented by $dp[i-2]$. The possible $1$ fall damage into mob $i-1$ is exactly why the cost uses $\max(1,h_{i-1}-1)$.

So the recurrence covers all optimal endings for the prefix. No hidden mega-combo is missing; the physics only lets the big damage cross one edge.

Complexity

Each mob is processed once.

$$O(n)$$

per test case, and

$$O\left(\sum n\right)$$

over all test cases. Use long long, because health can be $10^9$ and there can be $2\cdot 10^5$ mobs. Ints will faceplant.