help in a dp problem.

general
1

prob : http://codeforces.com/problemset/problem/478/D

I’ve read the comment and they have talked about dp[i][j] = no. of ways of having ‘i’ height using ‘j’ red blocks. But I didn’t understand what about blue blocks? according to this number of blue blocks are the remaining blocks but how can we sure about the fact that sufficient number of blue blocks are available?

2

My dear friend, we only need to write a judgment statement on how to determine whether the blue block is enough. For such dp state, we will not use it for state transition and ignore them in the final answer.

3

I think i’m missing something. we are answering the number of ways we can make i height tower with j red blocks. where are we imposing constraint on bluw blocks?

4

once the values of all the states dp[i][j] are found, you will only add a state to the answer if i*(i+1)/2 - j <= the number of blocks of the other color that are left. I think that’s what @freeloop meant.

5

thanks for the reply!