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.
