|
|
back to boardTell me please! Is it greedy??? Greedy only? I think. I don't solve else but think that next algo is right: 1. maximal production =d in all n periods; 2. Greedy approach :satisfy first demand as fully as possible; 3. If we have residue in last period equal to k diminish by k residues in previous periods until it is possible 4. Sum final residues along all periods. Edited by author 26.10.2008 20:52 My algo is the same as your! (but still wa 15) :-( You definitely need reading math eco theory optimal store managing(Taha a.s.o.) P.S.I also have WA14. First number of output I guarantee but the second need more delicate algo. may be your problem with the type of the second number(it should be __int64)??? Maxim Dvoynishnikov (Dnipropetrovsk SU) * [1] // Problem 1648. Yachts 27 Oct 2008 01:32 I have WA49 with greedy and restroring. use int64(long long) ,then you'll get AC. Yuare right! With __int 64 AC. I didn'r recognized masked danger:100000*100000=10*1-e9. All data seemed fitted in int type. Edited by author 27.10.2008 09:21 Are you got AC with your algo or you had chaged it??? Edited by author 28.10.2008 14:51 I considered stored values backward more attentievely according with alg: store[i-1]=max(store[i]+sell[i-1]-d,0) store[n]:=0; i=n..1 where sell[i-1] array of greedy selling on the first stage. Accepted!!!!!! this test help me find my bug... in: 5 5 3 1 20 3 10 out: 25 10 and now,after accepted, could somebody, who solved this problem with DP, sent to me your solution? my mail: asyamov@mail.ru Edited by author 28.10.2008 16:18 I think greedy can work well. I don'n understand, how to solve this problem whith DP or greedy. I solve with RMQ. |
|
|