Subtask 1, 2

Ta có thể dùng quay lui để mô phỏng thực hiện tìm tất cả đường đi có thể để giải cứu công chúa, với cách làm này ta có thể AC được subtask 1 với kích thước dữ liệu nhỏ, và subtask 2 do chỉ có một đường đi duy nhất đến màn chơi \(n\).

Subtask 3

Ta xem mỗi màn chơi như một đỉnh của đồ thị, và các cánh cổng là một cung của đồ thị đó. Do các cánh cổng đều chỉ cho phép đi từ một màn chơi đến màn chơi có chỉ số lớn hơn (\(v_i < t_i\)). Vậy nên ta dễ dàng nhìn ra đây là một đa đồ thị có hướng không chu trình (DAG).

Từ đây ta có thể nhận thấy rằng bài toán này có thể được giải bằng quy hoạch động như sau:

• Gọi \(dp[u]\) là điểm sức mạnh tối đa có thể đạt được sau khi vượt qua màn chơi \(u\)
• \(dp[1] = p\)
• $
  dp[t_i] = \begin{cases}
  dp[v_i] + \lfloor l_i/2 \rfloor && \text{nếu } dp[v_i] > l_i\
  dp[v_i] - \lfloor dp[v_i]/2 \rfloor && \text{ngược lại}
  \end{cases}
  $
• Ta dùng \(dp[n]\) so sánh với \(D\) rồi đưa ra đáp án.