Обсуждение @ 1029. Министерство @ Timus Online Judge

karan Approach [3] // Задача 1029. Министерство 28 авг 2013 17:59

I used dijkstra to do in O(mnlog(mn))? Whats your approach?

Nikunj Banka I used dp [1] // Задача 1029. Министерство 14 окт 2013 15:16

I used dynamic programming to solve the question.
dp[floor][room][lastStep] indicates the best way to reach top when we are on floor, room and the last step is know. Each state of dp is solved in constant time as we have to do only 2 computations at each step. But my approach runs very very slow.

Giorgi Dzamashvili Re: I used dp // Задача 1029. Министерство 29 окт 2013 02:39

Two dimensions are enough

Han Lin Re: Approach // Задача 1029. Министерство 9 апр 2014 12:24

DP can solve this problem in O(MN).

Обсуждение задачи 1029. Министерство