You have mined a large slab of marble from a quarry. For simplicity, suppose the marble slab is a rectangle measuring n inches in height and m inches in width. You want to cut the slab into smaller rectangles of various sizes - some for kitchen countertops, some for large sculpture projects, others for memorial headstones. You have a marble saw that can make either horizontal or vertical cuts across any rectangular slab.
At any time, you can query the spot price P(x, y) of an x-inch by y-inch marble rectangle, for any positive integers x and y. These prices depend on customer demand, and people who buy marble countertops are weird, so don't make any assumptions about them; in particular, larger rectangles may have significantly smaller spot prices. Given the array of spot prices and the integers m and n as input, design a dynamic programming algorithm to compute how to subdivide an n x m marble slab to maximize your profit.
Your solution must output both the maximum profit as well as the sequence of cuts necessary to obtain that profit. A sequence of cuts can be described as a sequence of tuples (V, x, y_min, y_max) for vertical cuts, (H, y, x_min, x_max) of horizontal cuts.
Make your solution as asymptotically efficient as you can; we are not providing any particular target.