Discussion @ 1437. Gasoline Station @ Timus Online Judge

I use DFS, how to solve it by DP?

Posted by hliu20 26 May 2013 18:56

DFS, record the state, if come into a state appeared before , ignore it.
DFS is very slow, can anybody give some hints to DP?

Re: I use DFS, how to solve it by DP?

Posted by Felix_Mate 13 Jul 2015 10:21

Это и есть ДП. Ведь ты переходишь по сути в известные состояния(т.е.уже просмотренные) и новые,для которых рассматриваешь переходы.Просто у нас не совсем стандартные размерности "подзадачи".
ДП-это не только реккурентные соотношения.

Discussion of Problem 1437. Gasoline Station