11908 - Skyscraper

[asif_iut]

i tried to solve this problem using dp but how can i store the dp results in a table?? a N X N array exceeds the memory limit

[crip121]

greedy will do..

[Taman]

Spoiler
I got accepted by implementing O(N) dp. think that when I am thinking from i'th floor, suppose I can place an advertisement that is x floors long and have a profit of p unit. so profit[i+x]=max(profit[i+x],profit[i-1]+p);

P.S.: please don't misunderstand,this is copy-pasted from Topcoder forum. and that post was also by me :p

[crip121]

after reading taman's post, i looked at my code again and cant decide whether it would be dp or greedy. but i think its a close resembelance to LIS algorithm with a bit of greedy choice. sorry if it makes anyone misguided.
here's my algo,

1. sort (criteria is yours to decide)
2. now, for i'th position you have either two choice(dp)
- place it (how, well greedy comes here, just look back a bit)
- or the previous profit is better

i used N^2 time complexity with N memory, but it can be done in NlogN too.

[zobayer]

this is not good to give the solutions even if no one has asked. please remove your spoilers.

it is quite sufficient when you state the complexity or something like "dp will do"

however, it can be solved in O(n) + O(n lg n) which is in total O(n lg n) time, and O(n) memory.
there are two ways, straight forward dp, or u can also use binary search subroutine. The first one turns out to be faster.

[naseef_07cuet]

Please delete your post.Who have given the solution.It is not good for others to have solution without solving it.I think this is an easy greedy problem.But one have to be careful about the time.

Happy Coding.

[amin__]

hello I am getting wa in this problem and need some critical cases..Can anyone help me??