USACO 4.2 (IOI'96) — Job Processing

Правка en1, от determinism, 2015-07-02 16:02:37

I couldn't prove the greedy algorithm which used in the A part of this problem, so I looked it up on the internet and found (this)[http://blog.m-s-t.org/2012/12/27/usaco-4-2-job-processing-analysis/]. There is a proof there, but I think that it's incomplete. Specifically, it doesn't prove subproblem needs to be solved optimally for problem to be solved optimally. Thanks for help in advance.

Also, I'm really bad at greedy algorithms. Is there any text on proof techniques for greedy algorithms, must-solve problems, or other important stuff on greedy algorithms you know?

Теги greedy, ioi

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en3 Английский determinism 2015-07-02 16:31:26 3 Tiny change: 'thm which used in t' -> 'thm which is used in t'
en2 Английский determinism 2015-07-02 16:03:09 71
en1 Английский determinism 2015-07-02 16:02:37 612 Initial revision (published)