Dynamic programming


  • 0
    S

    Problem : Aesthetic Building Modification
    Launch Code Editor
    There are N consecutive buildings in a society. The owners decided to increase the heights of the buildings. Being aesthetically
    oriented, they wanted to ensure that the heights (all measured as number of floors in the building) of consecutive buildings differ
    at most by one floor so that the skyline of the buildings look pleasing. It is also desired that after the increase of heights, the
    profile of the entire society will look like an inverted "V" - that is the heights will increase up to the middle building and thereafter
    the height will decrease steadily. In other words, for p < N/2, the heights of the buildings after modification will satisfy the
    condition H p+1 - H p = 1 and for p > N/2, the heights will satisfy H p - H p+1 = 1.
    Notifications
    Status messages
    The cost of increase is computed as follows. Let f be the function defined by f(x) = 1000 max(x,1) 2 . That is f(10) = 100000 while
    f(-10) = 1000.
    To increase the height by h > 0 floors, the total cost is
    f(B) + f(B-1) + f(B-2) + .... + f(B-(h-1))
    where B is a given base cost.
    We cannot decrease the height of any building. If the number of buildings is even, there will be two buildings at the middle point
    with the same height and their height will be the highest.
    Input Format:
    First line containing an integer T, the number of test cases.
    In the next T pairs of lines each pair containing an integer N and a base price B.
    A second line containing space separated N integers containing heights of the N buildings in order.
    Output Format:
    T lines where ith line contains the minimum cost required for the ith test case.
    Constraints:
    1 ≤ N ≤ 10 3
    1 ≤ H i ≤250
    1 ≤ B ≤ 10 3
    Example 1
    Input
    1
    6 5
    2 6 11 5 3 1
    Output
    282000
    Explanation
    Initially, the height of 6 buildings are [2 6 11 5 3 1]
    For the first n/2 elements, criteria is: Hp+1 - Hp=1
    Consider the height of first 3 buildings [2 6 11], so it becomes [9 10 11]
    So the height of the next building should be 11. Also the heights of the last n/2 buildings should be [11 10 9] and thus the final
    heights of the buildings are [9 10 11 11 10 9]
    For building 1,
    Increase in height is 7 and the cost is
    f(5) + f(4) + f(3) + f(2) + f(1) + f(0) + f(-1)=1000(5 2 +4 2 +3 2 +2 2 +1 2 +1 2 +1 2 =25+16+9+4+1+1+1)=57000 rupees
    In the same way,
    For building 2, cost=54000 rupees
    For building 3, cost= 0 rupees
    For building 4, cost= 56000 rupees
    For building 5, cost= 57000 rupees
    For building 6, cost= 58000 rupees
    Total cost required 282000 rupees


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.