N개의 블록이 순서대로 있는데

부분수열처럼 각 블록의 순서는 뒤바꿀 수 없고 (중간의 몇 개를 빼는 식으로, 1번 5번 6번 9번 이렇게 쌓는 식)

인접한 블록을 연속으로 쌓을 때는 블록의 구멍이 딱 맞아서 두 블록 자체의 높이 빼기 아래 블록의 구멍 깊이만큼이 두 블록의 높이가 됨

그리고 전체 높이가 일정 높이 이하여야 함


예를 들어서 최대 높이가 H, i번째 블록 높이가 h_i, 깊이가 d_i라고 하면

1, 3, 4, 7 블록을 쌓은 건 h1+h3-d3+h4+h7 <= H인 식으로


이런 경우의 수가 총 몇 개인지 구해야 하는데 단순히 재귀적으로 짜니까 지수함수 꼴에 가깝게 나오네

각 블록에 대해서 들어가거나 들어가지 않는 식으로 2^N...


원래는 특정 i번째 블록을 기준으로 잡아서 1~i-2번째 블록이 H-h_i 이하의 높이로 쌓이는 가짓수랑 

i-1번째 블록을 무조건 쌓고 그 아래로 1~i-2번째 블록에 대해 저 i번째 블록에 대해 한 것처럼 점화식으로 하고 하는 식으로 생각해보려다가

( G(i, H) = F(i-2, H-h_i) + G(i-1, H-h_i-1+d_i-1-h_i) 같은 식으로)

어차피 특정 높이에 따라서 i+1번쨰 블록부터 어떻게 쌓을지 가짓수가 달라져서 의미가 없는 거 같기도 하고...


뭔가 좀 아이디어 없을까