* Problema do corte de haste * (Cormen, 3ª ed, §15.1)

1. DEFINIÇÃO DO PROBLEMA: encontrar a melhor maneira de cortar uma haste de
   tamanho "n" em pedaços inteiros, de forma a maximizar o lucro obtido. Cada
   pedaço de tamanho "i" tem preço p[i].

2. Um algoritmo de programação dinâmica para a versão simplificada do problema:

==================================================
Algoritmo: corte_simpl
Entrada: p[1..n] de reais não-negativos.
Saída: um número real // o maior lucro possível
--------------------------------------------------
1. L[1] := p[1]
2. PARA t DE 2 A n
3. | M := p[t]
4. | PARA i DE 1 A t-1
5. | | l := p[i] + L[t-i]
6. | | SE M < l
7. | | | M := l
8. | L[t] := M
9. RETORNE L[n].
==================================================

3. Um algoritmo de programação dinâmica que retorna a solução completa:

==================================================
Algoritmo: corte_compl
Entrada: p[1..n] de reais não-negativos.
Saída: um número real e um vetor de inteiros.
--------------------------------------------------
1. PARA t DE 1 A n
2. | L[t] := p[t] , V[t] := t
3. | PARA i DE 1 A t-1
4. | | l := p[i] + L[t-i]
5. | | SE L[t] < l
6. | | | L[t] := l , V[t] := i
7. RETORNE (L[n],V).
==================================================

4. EXERCÍCIO: É correto substituir "t-1" por "piso(t/2)" na linha 4?
              Isso diminui a complexidade do algoritmo?