Блог пользователя prithviking98

Proof for a greedy solution
Автор prithviking98, история, 6 лет назад, По-английски

the problem is UVa 11157 — lazy frog

i understand that the subproblem is to find the minimax jump between two closest big stones. but how to prove that alternating jumps on the small stones is the best strategy ?

  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

»
6 лет назад, # |
  Проголосовать: нравится +14 Проголосовать: не нравится

Let us prove this by contradiction. Let this not be the optimal strategy and the maximum jump is Mi - 1 → Mi + 1. Using optimal solution frog will jump:

  • Mi - 1 → Mi frog must jump Mi - 2 → Mi + 1 — greater distance than Mi - 1 → Mi + 1;

  • Mi → Mi + 1 frog must jump Mi - 1 → Mi + 2 — greater distance than Mi - 1 → Mi + 1.

We got a contradiction, so your greedy is correct.

→ Ответить