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 <[email protected]>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 <[email protected]>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 <[email protected]> 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 > [email protected]. > 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 [email protected]. For more options, visit https://groups.google.com/groups/opt_out.
