Help needed in a DP Optimisation Problem

Revision en5, by bhishma, 2017-07-23 11:42:12

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

  1. 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.

  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 jth 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

Can someone help me in optimising this recurrence relation.

Tags dp optimisation, usaco, poj

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en8 English bhishma 2017-07-26 23:19:55 257 Solved
en7 English bhishma 2017-07-24 16:20:18 4 changed base case 2
en6 English bhishma 2017-07-23 16:51:14 2
en5 English bhishma 2017-07-23 11:42:12 81 (published)
en4 English bhishma 2017-07-23 11:40:28 93
en3 English bhishma 2017-07-23 11:36:18 572 Tiny change: 'g_white%20%5Clarge%20DP%5Bi' -> 'g_white%20DP%5Bi'
en2 English bhishma 2017-07-23 11:01:58 555
en1 English bhishma 2017-07-23 10:46:28 438 Initial revision (saved to drafts)