Faced this problem in practice area : Problem
It seems like a general DP problem but I could not figure out its solution.I also tried finding its editorial but there seem to be no resource available for this problem.I tried seeing solutions of others but they were impossible to understand until I know what does DP array in their solution represent.
So please help me.Any small hint will also do fine. Thanks in advance. :)
The idea is that if after painting the first i fences, if you know how much paint left from one color, you can calculate how much paint left from the other. So it's enough to store how much left from one of the two paints in your DP state.
Assume you have x left from the first paint after painting the first i fences, then the amount left from the second paint:
y = b - sumi + (a - x)
(sumi is the sum of the heights of the first i fences)
DP[i][j][0] = minimum unattractiveness value achieved by painting the first i fences, while the last fence is painted with the first color, and having j left from the first paint.
If you have enough paint from the first color to cover (i+1)th fence:
DP[i + 1][j - h[i + 1]][0] = min(DP[i + 1][j - h[i + 1]][0], DP[i][j][0])
If you have enough paint from the second color to cover (i+1)th fence:
DP[i + 1][j][1] = min(DP[i + 1][j][1], DP[i][j][0] + min(h[i], h[i + 1]))
DP[i][j][1] = minimum unattractiveness value achieved by painting the first i fences, while the last fence is painted with the second color, and having j left from the first paint.
If you have enough paint from the first color to cover (i+1)th fence:
DP[i + 1][j - h[i + 1]][0] = min(DP[i + 1][j - h[i + 1]][0], DP[i][j][1] + min(h[i], h[i + 1]))
If you have enough paint from the second color to cover (i+1)th fence:
DP[i + 1][j][1] = min(DP[i + 1][j][1], DP[i][j][1])
Code: 15608339
Thanks a ton :)