I've been stuck on this problem for a while (Lazy Cows USACO 2005 US Open Gold) . I was able to get the recurrence correct . But my naive approach () TLEs .
First I compressed the positions by sorting them based on their column and breaking ties using the row number
Then I pre-processed 3 arrays
costH1[i][j] stores minimum area covered using a single horizontal rectangle , from ith smallest position to jth . If it's not possible (cows are not entirely up or entirely down) then its INF.
costH2[i][j] stores minimum area covered using 2 horizontal rectangles . If it can be covered with a single rectangle then its INF.
costV[i][j] stores minimum area covered using a single vertical rectangle . To be more precise , its a rectangle with top left coordinate at (1 , coordinate[i]) and bottom right at (2 , coordinate[j])
Using these 3 arrays
DP[i][j] stores the minimum area covered by i rectangles for a prefix area till jth column.
DP[j] = INF
DP[j] = min(costV[j], costH1[j])
DP[i] = 0
My Submission : Commented Code
Can someone help me in optimising this recurrence relation.