Блог пользователя Eddagdeg

Автор Eddagdeg, история, 5 лет назад, По-английски

Hello! There is a field n×m, and k of its cells are impassable walls. A robot is initially at the cell (1,1) (bottom left). The robot can only move right or up, and eventually it needs to get into the cell (n,m), avoiding all obstacles. You need to count the number of ways he can do it. Assume that the sizes n and m are very large (say, 109), and the number k is small (around 100) how to solve that in o(k^3)? any hint please and thanks!

  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

https://codeforces.com/blog/entry/47764

Read the part "Change object to DP"