Constructing Matches Qual 1 2007

TCCC Qual 1 yesterday, with 28 minutes left to work on 1000 ptr, I had mentally throw in the towel. I've been saying to myself I could not do this in less than half an hour. This problem looks very complicated at that time. I could not think of a way to approach it, and keep saying to myself it's impossible to do it within time frame, so I decided to roll my tobacco and smoke outside instead of working on it.

When its already too late, somehow I see the DP problem is not too complicated. Just construct the match from left to right, by first putting two vertical matches at the top and the bottom row, to make left wall of current column. Every DP step try all possible 3 horizontal matches to fill the column. Having two left vertical matches on the left wall and 3 horizontal matches, the next 2 vertical matches can be determined based on this 5 choices of matches, and the requirements of the weight of both top and bottom rectangles. Here is a sample code, which might explain better than my words.
What I had in mind when writing that code can (hopefully) be visualized with the diagram. The red ones are the previous Dynamic Programming step, blue ones are the next sub problem we'll deal later. During calculation of each steps, we know somehow the dp algorithm reach a state where matches top & bot are left vertical wall for the current column. We tried all possible horizontal (i,j,k) matches, and continue to check cost of building the next column if possible (possible means the restriction on weights are not violated). We then choose minimum of all these sub problems.