As a competitive programmer and League player, I feel obligated to share my thought process. Pretty sure I've arrived at the correct solution.

It's easy to see that this is a Dynamic Programming problem. Now how do we define our DP state? Well, the base case is pretty clear - stop when all minions are dead.

For each monster - we have two choices. Either we let Diana shoot any monster, or we let the tower shoot the monster we are currently at. Let the monster we are currently at be monster i.

In order to craft a solution, let's concretely define how we think of Diana shooting a monster. Technically, Diana can shoot any monster numbered {i, i +1... N} for N monsters. Think of her shooting as a future move, that we can save up.

The tower is straightforward: it always shoots monster i, until it's dead - which is when it switches to the next monster.

With these observations, we can come up with the following dp state.

We can thus define a function F(i, j, k) which defines our algorithm. Let dp[i][j][k] be the maximum gold that we can earn where monster i has j health points remaining, and Diana has k tower shots saved.

if i > N:
    return 0 // all monsters poof
else if j > 0 && k:
    if j - P > 0 
        gEarned = 0
    else 
        gEarned = G[i]
    F[i][j][k] = max(F(i, j - Q, k + 1), gEarned + F(i, j - P, k - 1)) // we let the tower hit the minion,  or we hit it. if we kill the minion, we get gold
else:
    F[i][j][k] = F(i + 1, H[i + 1], k) // minion died before we did anything, move onto the next one

.. where gEarned is the gold we will earn in that move. All other notations are the same as that in the problem statement.

After memoization, the complexity of this solution will be O(N * Sum(H) * Max(k)). What is the maximum k? Funnily, it's 1000. (P, Q >= 20 and Sum(H) <= 20000). I apologize if I sounded unclear!

EDIT: Typo.

this is brute force having cases where diana hits every single minion so its like O(n²⁾ complexity?

this is brute force having cases where diana hits every single minion so its like O(n²⁾ complexity?

I think the solution is that Diana should stop stealing my minions and should gank my lane before I get 3v1 dived

But this is actually really cool brb gonna try it out

def cs_alg(minions, td, cd) # [[health, gold]], tower damage, champ damage
    gold_vals = minions.each_with_index.map { |x, i|
        m2 = minions.dup()
        m2[i][0] -= cd
        gold = m2[i][0] < 1 ? m2[i][1] : 0
        m2.delete(i) if m2[i][0] < 1
        m2[0][0] -= td
        m2.shift if m2[0][0] < 1
        cs_alg(m2, td, cd) + gold  
    }
    m2 = minions.dup()
    m2[0][0] -= td
    m2.shift if m2[0][0] < 1
    gold_vals.append(cs_alg(m2, td, cd))
    gold_vals.max
end

As a competitive programmer and League player, I feel obligated to share my thought process. Pretty sure I've arrived at the correct solution.

It's easy to see that this is a Dynamic Programming problem. Now how do we define our DP state? Well, the base case is pretty clear - stop when all minions are dead.

For each monster - we have two choices. Either we let Diana shoot any monster, or we let the tower shoot the monster we are currently at. Let the monster we are currently at be monster i.

In order to craft a solution, let's concretely define how we think of Diana shooting a monster. Technically, Diana can shoot any monster numbered {i, i +1... N} for N monsters. Think of her shooting as a future move, that we can save up.

The tower is straightforward: it always shoots monster i, until it's dead - which is when it switches to the next monster.

With these observations, we can come up with the following dp state.

We can thus define a function F(i, j, k) which defines our algorithm. Let dp[i][j][k] be the maximum gold that we can earn where monster i has j health points remaining, and Diana has k tower shots saved.

if i > N:
    return 0 // all monsters poof
else if j > 0 && k:
    if j - P > 0 
        gEarned = 0
    else 
        gEarned = G[i]
    F[i][j][k] = max(F(i, j - Q, k + 1), gEarned + F(i, j - P, k - 1)) // we let the tower hit the minion,  or we hit it. if we kill the minion, we get gold
else:
    F[i][j][k] = F(i + 1, H[i + 1], k) // minion died before we did anything, move onto the next one

.. where gEarned is the gold we will earn in that move. All other notations are the same as that in the problem statement.

After memoization, the complexity of this solution will be O(N * Sum(H) * Max(k)). What is the maximum k? Funnily, it's 1000. (P, Q >= 20 and Sum(H) <= 20000). I apologize if I sounded unclear!

EDIT: Typo.