by match u mean that number of fruits that overlap with i th fruit but are not sliced before time i. which means we have to consider 2^m cases where m is the maximum number of fruits that overlap with ith fruit. And this we have to do for each fruit.
On Mon, Jan 28, 2013 at 12:54 AM, Nikhil Karnwal <sunnyk12...@gmail.com>wrote: > 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. > > > -- 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 algogeeks+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/groups/opt_out.
