A harder version of the problem 1013F, Igor and Mountain

Revision en2, by Mousa_Aboubaker, 2025-03-25 23:10:05

when I was solving this problem, I thought that Igor can go directly to any cell in any row above his current row as long as the Euclidean distance between that cell and his current cell is less than or equal to $$$d$$$

but in the last minutes of the contest, I realized that he can only go to any cell in the row that is exactly above him if he can reach it

with this, I found the solution for the problem faster and I got AC

now, I'm wondering, how to solve this problem if Igor can go to any row as long as he satisfies the constraints ?

for example, in the second testcase, Igor can go from the last row to the first row as mentioned in the image above

the result should be 70

how many ways to reach the first row for each X cell

what is the optimal solution for such a problem ?

I'm looking forward to see your ideas and solutions, and thanks ^_^

Tags dp

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en4 English Mousa_Aboubaker 2025-03-25 23:15:14 0 (published)
en3 English Mousa_Aboubaker 2025-03-25 23:15:00 4 Tiny change: ' 3 0 2\n0 10 10 0\n0 35 0 3' -> ' 3 0 2\n\n0 10 10 0\n\n0 35 0 3' (saved to drafts)
en2 English Mousa_Aboubaker 2025-03-25 23:10:05 0 (published)
en1 English Mousa_Aboubaker 2025-03-25 23:07:53 1124 Initial revision (saved to drafts)