Note the value of j is never decreasing
On Jan 7, 8:56 pm, sourabh jakhar <sourabhjak...@gmail.com> wrote:
> it is a o(n2) complexity
>
>
>
> On Fri, Jan 7, 2011 at 6:13 PM, emacs ray <emacs...@gmail.com> wrote:
> > Here is an O(n) approach without any advanced data structures.
>
> > dp[i] = max{dp[j] : m[i]-m[j] >= n} + a[i]
>
> > With the increasing of i, the optimal value in the brace will
> > not be descending. We can keep the optimal value so far and check if
> > there is a larger one.
>
> > #include <iostream>
> > using namespace std;
>
> > int profit(int m[], int p[], int n)
> > {
> > int i,j,dp[7] = {0},k,mx = 0;
> > for(j = 0, i=0;i<7;i++)
> > {
> > for (; j < i && m[i]-m[j] >= n; j++)
> > if (dp[j] > mx)
> > mx = dp[j];
> > dp[i] = mx+p[i];
> > }
> > for(i=0;i<7;i++)
> > cout<<dp[i]<<endl;
> > for(i=0;i<7;i++)
> > if(mx<dp[i])
> > mx = dp[i];
> > return mx;
> > }
>
> > int main()
> > {
> > int m[7] = {1,3,5,8,9,12,15};
> > int p[7] = {5,9,1,6,2,8,3};
> > cout<<"\nThe maximun profit is : "<<profit(m,p,5); //
> > }
>
> > On Jan 5, 3:06 am, Decipher <ankurseth...@gmail.com> wrote:
> > > Yuckdonald's is considering opening a series of restaurants along
> > > Quaint Valley Highway (QVH).The n possible locations are along a
> > > straight line, and the distances of these locations from the start of
> > > QVH are, in miles and in increasing order,m1;m2; : : : ;mn. The
> > > constraints are as follows:
> > > 1)At each location,Yuckdonald's may open at most one restaurant.The
> > > expected profi t from opening a restaurant at location i is pi, where
> > > pi > 0 and i = 1; 2; : : : ; n.
> > > 2)Any two restaurants should be at least k miles apart, where k is a
> > > positive integer.
> > > Give an effi cient algorithm to compute the maximum expected total
> > > pro fit subject to the given
> > > constraints.
>
> > --
> > You received this message because you are subscribed to the Google Groups
> > "Algorithm Geeks" group.
> > To post to this group, send email to algoge...@googlegroups.com.
> > To unsubscribe from this group, send email to
> > algogeeks+unsubscr...@googlegroups.com<algogeeks%2bunsubscr...@googlegroups.com>
> > .
> > For more options, visit this group at
> >http://groups.google.com/group/algogeeks?hl=en.
>
> --
> SOURABH JAKHAR,(CSE)(3 year)
> ROOM NO 167 ,
> TILAK,HOSTEL
> 'MNNIT ALLAHABAD
>
> The Law of Win says, "Let's not do it your way or my way; let's do it the
> best way."
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
