Phân tích: Last Hit

Diana và trụ thay phiên nhau bắn \(N\) con quái vật và Diana được đi trước. Diana có thể bắn bất kỳ con quái vật nào hoặc bỏ qua lượt, trong khi trụ luôn bắn con quái vật gần trụ nhất. Mỗi con quái vật \(i\) bắt đầu với một lượng máu \(H_i\) nhất định, máu sẽ giảm \(P\) khi bị Diana bắn và giảm \(Q\) khi bị trụ bắn. Nếu máu xuống dưới \(1\), quái vật chết và không thể bị bắn thêm. Diana được thưởng \(G_i\) vàng nếu phát bắn của cô ấy tiêu diệt được quái vật thứ \(i\).

Quan sát then chốt ở đây là: đối với Diana, việc bắn một con quái vật khác với con quái vật hiện đang bị trụ nhắm tới hoàn toàn tương đương với việc không bắn bất kỳ con quái vật nào trong lượt này và thay vào đó nhận được một phát bắn "dư" để sử dụng ở lượt sau. Sau đó, Diana có thể sử dụng một số hoặc tất cả các phát bắn dư đã tích lũy của mình một cách liên tiếp. Vì vậy, thay vì đưa ra quyết định "mình nên bắn con quái vật nào?" trước mỗi phát bắn của trụ, Diana chỉ cần quyết định xem có nên sử dụng một trong các phát bắn dư của mình (lên con quái vật đang sống gần trụ nhất) hay để trụ thực hiện phát bắn.

Điều này đưa bài toán về lời giải quy hoạch động (DP) với trạng thái là: con quái vật hiện tại \(i\) đang nhắm tới, lượng máu còn lại của con quái vật hiện tại và số lượng phát bắn dư mà Diana đang có. Lưu ý rằng vì có giới hạn dưới cho \(P\) và \(Q\), số lượng phát bắn dư tối đa của Diana là khoảng 1000. Trong lời giải DP, có ba bước chuyển trạng thái:

1. Con quái vật hiện tại đã chết và chúng ta chuyển sang con quái vật tiếp theo.
2. Diana bỏ qua một phát bắn và nhận thêm một phát bắn dư (để trụ bắn một lần).
3. Diana bắn con quái vật một lần bằng cách sử dụng các phát bắn dư của mình, có thể tiêu diệt con quái vật hiện tại và nhận vàng của nó.

Dưới đây là mã giả cho quy hoạch động top-down với một số chú thích làm rõ:

# We are at monster i which has rem_hp HP left and Diana has
# extra_shots shots saved up, how much gold can she get?
function rec(i, rem_hp, extra_shots)
  # Base case: all monsters have been killed.
  if (rem_hp <= 0 && i + 1 == N) return 0

  # Monster i is dead, move on to the next one.
  if (rem_hp <= 0) return rec(i + 1, H[i + 1], extra_shots)

  # Memoization.
  if is_set(memo[i][rem_hp][extra_shots])
    return memo[i][rem_hp][extra_shots]

  # The tower shoots next. Diana saves up another shot.
  ret = rec(i, rem_hp - Q, extra_shots + 1)

  # Diana shoots next, using one of the saved up shots.
  # If the shot kills the current monster, she gets its gold.
  if (extra_shots > 0)
    gold = (rem_hp <= P) ? G[i] : 0
    ret = max(ret, gold + rec(i, rem_hp - P, extra_shots - 1))

  return memo[i][rem_hp][extra_shots] = ret


# Since Diana plays first, she has one extra shot initially.
print rec(0, H[0], 1)

Dựa trên phân tích chính thức của Google Code Jam.