# Dynamic programming

• 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.
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

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