Codeforces celebrates 10 years! We are pleased to announce the crowdfunding-campaign. Congratulate us by the link https://codeforces.com/10years. ×

### mokoto's blog

By mokoto, history, 4 weeks ago, ,

The problem Hills states that we have to build k houses where each house must be strictly greater than its neighbours.

Here is one accepted solution.

I am not able to get transitions. if dp[x][y][z] denotes minimum cost to build y houses upto index x, and z tells whether we are going to build house on index x or not.

Now if z == 0, it means we are not gonna build house at current index x.

	if (z==0)
{
int cost=0;
if (a[x-1]>=a[x]) cost+=(a[x-1]-a[x]+1);
if (a[x+1]>=a[x]) cost+=(a[x+1]-a[x]+1);
dp[x][y][z]=min(caldp(x+1,y,0),caldp(x+2,y-1,1)+cost);
}


Then according to above transition.My doubt is, why are we calculating caldp(x+2,y-1,1). since it means that we made a house at index x with some cost and can't build at index x+1 and recurring for x+2. But z = 0 means we are not building any house at index x.

&&&

	if(z!=0)
{
int cost=0;
if (min(a[x-2]-1,a[x-1])>=a[x]) cost+=(min(a[x-2]-1,a[x-1])-a[x]+1);
if (a[x+1]>=a[x]) cost+=(a[x+1]-a[x]+1);
dp[x][y][z]=min(caldp(x+1,y,0),caldp(x+2,y-1,1)+cost);
}



And if z != 0, it means we are gonna build house at index x, why the cost will not be only (a[x-1]-a[x]+1) + (a[x+1]-a[x]+1). Why in the above equation there is a comparision between min(a[x-2]-1,a[x-1] >= a[x]). again my doubt is if we build a house at index at then we have to lower hills of index x-1 and x+1, why we are taking index x-2 in consideration.

Please help. Stuck in this problem since 2 days, trying to understand, but not getting clear picture. Thanks.

• 0

 » 4 weeks ago, # | ← Rev. 2 →   +2 Thank you for trying to interpret my code.z in dp[x][y][z] is equal to 0 if a[x-1] is not changed, and is equal to 1 if a[x-1] is changed according to the height of a[x-2]Therefore, In the first case (z==0), the height of a[x-1] is a[x-1]. The additional cost to make a[x-1] lower than a[x] is (a[x-1]-a[x]+1) In the second case (z==1), the height of a[x-1] is lower than a[x-2] and is equal to min(a[x-2]-1,a[x-1]). The additional cost to make a[x-1] lower than a[x] is (min(a[x-2]-1,a[x-1])-a[x]+1)
•  » » 4 weeks ago, # ^ |   0 Thanks a lot. I understood it now. I was misinterpreting dp definition. Basically if previous height is not change we can either eastablish hill on current x or don't. similarly if prev. height is change and if we establish hill then we need to consider x -2 index also.Thanks. its very clear now.