| Показать все ветки Спрятать все ветки Показать все сообщения Спрятать все сообщения | | I solve with simple recursion!!!! | xurshid_n | 1381. Тараканы в здании | 13 авг 2012 14:47 | 1 | after 2 days, found DP solution, and AC with 0.046 s.
Edited by author 15.08.2012 16:07 | | WA 38. Something special? (-) | Vedernikoff Sergey (HSE: АОП) | 1381. Тараканы в здании | 16 мар 2012 01:36 | 2 | I think in this test there is some big loop with small weight. So u need go through cicle many times to decrease (increase) population of cockroaches. | | I don't understand, why this simple problem, solved only 25 coders! | EfremovAleksei | 1381. Тараканы в здании | 24 авг 2008 17:57 | 11 | I will try tomorrow and will be in one of two parties As for me, this problem has quite unusual idea. BTW, I heard what famous "hard life" has fairly simple solution :) May be you one of the best coders:) an it's simple for you? Could'n found very simple solution.
In final version calcul z1(k)= min [F(0,0,a1)+F(0,a1,a2)+
F(a1,a2,a3)+...+F(ak-1,ak,0)+F(ak,0,0)- a1-...-ak]
for all [a1....ak] k=1,....
z2(k)=min [-F(0,0,a1)-F(0,a1,a2)+
-F(a1,a2,a3)+...-F(ak-1,ak,0)+F(ak,0,0)+ a1-...+ak]
if (z1<0)&&(z2<0) <> and so on.
k from 1 to 10000 but functional depend only ak-1,ak
and z1(k-2). History fogotten this is "fishka" in my prog
Ac(1.3 cek) Ho make 0.015 don't now . AC(0.109) using DP, but i was really surprised, when my program got AC dp with bfs - i think it is very standart algo My method also standart.
It is Bellman-method for shortest path when
functional of length rather specific but have
main property of fogotten history I think, this method is DP It's quite obvious DP. Search for positive/negative loop around (0,0) in graph with transfers (i,j) -> (j,k) | | Sample#2 | Sandro | 1381. Тараканы в здании | 24 сен 2005 18:01 | 1 | Be careful! Sample input and output #2 have changed.
F(0,0,0)=0 in all tests in this problem. |
|
|
