Блог пользователя asif_iut

Автор asif_iut, 14 лет назад, По-английски
Given a list of advertisements for a building choose the ones which maximized the total income from the advertisements. Each advertisements spans the whole face of the building, so no two advertisements can occupy the same floor and no floors can be partially occupied.

Input starts with an integer N, denoting the total number of advertisements. Each advertisements is described using three integers, A ( 0 <= A <= 10 ^ 5 ) , B( 1 <= B <= 10 ^ 5 ) and C ( 1 <= C <= 1000 ) denoting the lowest floor of the advertisement, the number of floor the advertisement covers( including the lowest floor ) and the money earned from placing it, respectively.


Sample Input:
3
1 5 1
2 10 3
7 12 1

Ans : 3

how can this problem be solved ?
  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Sort the ads by their lowest floors and then you can do a DP.
If you want to use an ad, think of what all the ads it'll block.
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
the problem i faced during the contest is to keep the records of the advertisements states. which ads cannot be taken as a result of picking an ad.
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
In the contest We tried  binary search + dp . But could not  got AC.May be a bug in binary search . Binary search was to find  " if we take ad i which next ad we can take ".

14 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится
EDIT:

Ok I realised Sanzee's solution is the same XD