I've been stuck on this problem for a while [(Lazy Cows USACO 2005 US Open Gold)](http://poj.org/problem?id=2430) . I was able to get the recurrence correct . But my naive approach ( $\mathcal{O}(N^2 K)$ ) 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 ↵
↵
1. $costH1[i][j]$ stores minimum area covered using a single horizontal rectangle , from $i^{th}$ smallest position to $j^{th}$ . If it's not possible (cows are not entirely up or entirely down) then its $INF$.↵
↵
2. $costH2[i][j]$ stores minimum area covered using 2 horizontal rectangles . If it can be covered with a single rectangle then its $INF$.↵
↵
3. $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 $j^th$ column.↵
↵
↵
↵
Base Case↵
↵
$DP[0][j] = INF$↵
↵
$DP[1][j] = min(costV[0][i] , costH1[0][i])$↵
↵
$DP[i][0] = 0$↵
↵
My Submission : [Commented Code](https://gist.github.com/bhi5hmaraj/9e71d061325df12ca1087be0ee52325c)↵
↵
Can someone help me in optimising this recurrence relation.
↵
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 ↵
↵
1. $costH1[i][j]$ stores minimum area covered using a single horizontal rectangle , from $i^{th}$ smallest position to $j^{th}$ . If it's not possible (cows are not entirely up or entirely down) then its $INF$.↵
↵
2. $costH2[i][j]$ stores minimum area covered using 2 horizontal rectangles . If it can be covered with a single rectangle then its $INF$.↵
↵
3. $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 $j^th$ column.↵
↵
↵
↵
Base Case↵
↵
$DP[0][j] = INF$↵
↵
$DP[1][j] = min(costV[0][i] , costH1[0][i])$↵
↵
$DP[i][0] = 0$↵
↵
My Submission : [Commented Code](https://gist.github.com/bhi5hmaraj/9e71d061325df12ca1087be0ee52325c)↵
↵
Can someone help me in optimising this recurrence relation.
