Actually dp[i] represent the state in which u make a slice at appearing time of i th fruits.and match represent the overlapping fruits with i. so for each i dp[i]=max(dp[i],dp[j]+match); for all j=[0,i] and match =overlapped fruits with i which are not sliced until the cut of j. Hope this will help. Thanks
On Thu, Jan 24, 2013 at 10:18 PM, foram lakhani <foramlakh...@gmail.com>wrote: > Thanx for the reply but I didnt get you. What does dp[i] represent ? > > > On Thu, Jan 24, 2013 at 9:50 PM, sunny <sharadsin...@gmail.com> wrote: > >> take a structure or pair of start time and finish time and then sort the >> the structure you know the comparator function the for each for each dp[i] >> select j belongs to (0,i) and then count the overlap value >> >> >> if(j==0) >> dp[i]=max(dp[i],match); >> else >> dp[i]=max(dp[i],dp[j-1]+match); >> >> >> with this recursive relation my code got accepted in .24 sec others >> approach you mentioned may lead to the TLE >> >> On Thursday, January 24, 2013 1:35:38 PM UTC+5:30, emmy wrote: >>> >>> please help me with the following problem: >>> http://www.spoj.com/problems/**JUICE/<http://www.spoj.com/problems/JUICE/> >>> >>> bit mask will require very large memory. >>> If I sort the intervals in decreasing order of their start time.. I >>> still cant make it to a dp >>> If I sort the intervals in decreasing order of their finish times I am >>> still not getting a recurrence for dp that is valid >>> If I convert this to an interval graph, I have to find the maximum >>> number of vertices that can be included in some clique of size >=3. But >>> this also seems like a brute force approach. >>> >>> Which approach to try?? please help!! >>> >>> -- >> >> >> > > -- > > > -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/groups/opt_out.
