@immars , can you explain with some example or algorithm ? Thanks Shashank
On Tuesday, February 5, 2013 9:14:03 AM UTC+5:30, immars wrote: > > suppose: > > v : array of guards' request > > P(n): our problem: least coin spent until guard n, according to these rules > > M(n, x): least coin possibly combined equal to or larger than x until > guard n > > then: > > P(n) = min(P(n-1)+v[n], M(n-1, v[n])) > M(n, x) = min(M(n-1, x), M(n-1, x-v[n]) + v[n]) > > On Monday, February 4, 2013 8:24:19 PM UTC+8, marti wrote: >> >> You have N guards in a line each with a demand of coins.You can skip >> paying a guard only if his demand is lesser than what you have totally paid >> before reaching him.Find the least number of coins you spend to cross all >> guards. >> I think its a DP problem but cant come up with a formula.Another approach >> would be to binary search on the answer but how do I verify if no. of coins >> is a possible answer? >> > -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To unsubscribe from this group and stop receiving emails from it, send an email to [email protected]. For more options, visit https://groups.google.com/groups/opt_out.
