Help needed in a DP Optimisation Problem

Правка en1, от bhishma, 2017-07-23 10:46:28

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

Теги dp optimisation, usaco, poj

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en8 Английский bhishma 2017-07-26 23:19:55 257 Solved
en7 Английский bhishma 2017-07-24 16:20:18 4 changed base case 2
en6 Английский bhishma 2017-07-23 16:51:14 2
en5 Английский bhishma 2017-07-23 11:42:12 81 (published)
en4 Английский bhishma 2017-07-23 11:40:28 93
en3 Английский bhishma 2017-07-23 11:36:18 572 Tiny change: 'g_white%20%5Clarge%20DP%5Bi' -> 'g_white%20DP%5Bi'
en2 Английский bhishma 2017-07-23 11:01:58 555
en1 Английский bhishma 2017-07-23 10:46:28 438 Initial revision (saved to drafts)